前言

本章總結：從靜態和動態分別進行順序表的創建、插入、刪除、以及實例分析

1、創建順序表

1、靜態地生成一張順序表

#define MaxSize=100;
ElemType Sqlist[MaxSize];
int len;
//len表示順序表的長度

2、動態地生成一張順序表

#define MaxSize 10typedef int ElemType;	typedef struct{int *elem;		//指向順序表首地址elemint length;		//順序表中表的長度(元素個數)int listsize;	//順序表的存儲空間容量
}Sqlist;
void initSqlist(Sqlist* L)
{L->elem = (int*)malloc(MaxSize*sizeof(ElemType));	//開辟內存，并將該段空間首地址賦值給L->elemif (!L->elem){printf("分配內存失敗");exit(0);}						//如果分配內存失敗，返回L->length = 0;										//生成一張空的順序表L->listsize = MaxSize;
}

靜態定義，表占用的內存空間開辟在內存的靜態區，也就是函數棧上，該區域的從內存空間會隨著函數調用的完成而被系統自動回收。動態生成一個順序表，內存空間開辟在內存的動態區上，也就是堆內存上，這個區域的內存空間不會被系統自動回收，需要程序主動釋放.

2、順序表插入元素

在長度為n的順序表中的第i個位置插入新元素item

1、靜態表

void InsertElem(ElemType Sqlist[],int &n,int i,ElemType item)
{//向順表中Sqlist中第i個位置插入元素item,順序表原長為nint t;if(n==MaxSize || i<1 ||i>n+1)	exit(0);	//非法插入：判斷插入元素的位置是否對，或者表是否已滿，因為表的內存大小是固定不變的。for(t=n-1;t>=i-1;t--)	Sqlist[t+1]=Sqlist[t];		//將i-1后的元素往后移動一個元素Sqlist[i-1]=item;				//在i位置上插入元素itemn=n+1;							//數組長度+1
}

2、動態表,如果順序表已滿，可以追加一段內存空間

void InsertElem(Sqlist* L, int i, ElemType item)
{//向順序表L中第i個位置插入元素itemElemType* base, * insertPtr, * p;if (i<1 || i>L->length + 1){printf("非法插入");exit(0);}	//非法插入if (L->length >= L->listsize){base = (ElemType*)realloc(L->elem, (L->listsize + 10) * sizeof(ElemType));//重新追加空間L->elem = base;		//更新內存基地址L->listsize = L->listsize + 100;		//存儲空間增大100單元}insertPtr = &(L->elem[i - 1]);		//insertPtr為插入位置for (p = &(L->elem[L->length - 1]);p >= insertPtr;p--)*(p + 1) = *p;						//將i-1以后的元素順序往后移動一個元素位置*insertPtr = item;					//在第i個位置插入元素L->length++;
}

3、順序表刪除元素

刪除第i個位置元素的方法：將第i個位置以后的元素依次前移，從而覆蓋掉第i個元素

1、靜態表

void DelElem(ElemType Sqlist[],int &n,int i)
{int j;if(i<1 || i>n) exit(0);		//非法刪除、for(j=i;j<n;j++)Sqlist[j-1]=Sqlist[j];//將第i個位置以后的元素依次前移n--;		//表長-1
}

2、動態表

void DelElem(Sqlist* L, int i)
{ElemType* delItem, * q;if (i<1 || i>L->length){printf("非法刪除");exit(0);}delItem = &(L->elem[i - 1]);	//delItem指向表中第i個元素q = L->elem + L->length - 1;			//q指向表尾for (++delItem;delItem <= q;++delItem)*(delItem - 1) = *delItem;		//將第i位置以后的元素依次前移L->length--;				//表長-1
}

4、順序表實例分析

1、靜態

題目要求：
創建一個靜態的順序表存放整數，大小為10，完成以下操作：
1、輸入6個整數，打印出順序表中的內容，并顯示表中剩余的空間個數
2、在順序表中第3個位置插入元素0，打印出順序表中的內容，并顯示表中剩余的空間個數
3、試圖向表中第11個位置插入整數0，程序提示超出范圍
4、刪除表中的第6個元素，打印出順序表中的內容，并顯示表中剩余的空間個數

#include "stdio.h"
#define MaxSize 10//基本操作//
//向順序表中插入元素  Sqlist:表首地址 *len:表的長度  i:待插入元素的位置 x:待插入元素的元素值
void insertElem(int Sqlist[], int* len, int i, int x)
{int t;if (i<1 || i> * len + 1 || *len == MaxSize)	//非法插入操作，或者數組元素已滿{printf("This insert is illegal\n");return;}for (t = *len - 1;t >= i - 1;t--)Sqlist[t + 1] = Sqlist[t];Sqlist[i - 1] = x;			//插入元素*len = *len + 1;
}
//向順序表中刪除元素 Sqlist:表首地址	*len:表的長度 i:插入元素的位置
void DelElem(int Sqlist[], int* len, int i)
{int j;if (i<1 || i>*len){printf("This insert is illgel\n");return;}for (j = i;j <= *len - 1;j++)Sqlist[j - 1] = Sqlist[j];*len = *len - 1;
}
void show_sqlist(int Sqlist[],int len)
{int i = 0;for (i = 0;i < len;i++)printf("%d", Sqlist[i]);
}
//測試函數
int main()
{int Sqlist[MaxSize];	//定義一個靜態順序表int len=0;int i;printf("please input six interger number\n");for (i = 0;i < 6;i++){scanf("%d", &Sqlist[i]);len++;}show_sqlist(Sqlist, len);printf("\nthe spare length is %d\n", MaxSize - len);insertElem(Sqlist, &len, 3, 0);show_sqlist(Sqlist, len);insertElem(Sqlist, &len, 11, 0);		//在表中第11位置插入整數0DelElem(Sqlist, &len, 6);show_sqlist(Sqlist, len);printf("\nthe spare length is %d\n", MaxSize - len);return 0;
}

result：
在這里插入圖片描述

2、動態

編寫一個程序，動態的創建一個順序表。
要求：
1、順序表初始長度為10，向順序表中輸入15個整數，并打印出來
2、再刪除順序表中的第五個元素，打印出刪除后的結果

/*
編寫一個程序，動態的創建一個順序表。
要求：
1、順序表初始長度為10，向順序表中輸入15個整數，并打印出來
2、再刪除順序表中的第五個元素，打印出刪除后的結果
*/
#include "stdio.h"
#include "conio.h"
#include "malloc.h"
#include <stdlib.h>
#define MaxSize 10typedef int ElemType;	typedef struct{int *elem;		//指向順序表首地址elemint length;		//順序表中表的長度(元素個數)int listsize;	//順序表的存儲空間容量
}Sqlist;//初始化一個順序表
void initSqlist(Sqlist* L)
{L->elem = (int*)malloc(MaxSize*sizeof(ElemType));	//開辟內存，并將該段空間首地址賦值給L->elemif (!L->elem){printf("分配內存失敗");exit(0);}						//如果分配內存失敗，返回L->length = 0;										//生成一張空的順序表L->listsize = MaxSize;
}
/*
L：Sqlist類型指針
i：插入元素的位置
item:插入的元素
*/
void InsertElem(Sqlist* L, int i, ElemType item)
{//向順序表L中第i個位置插入元素itemElemType* base, * insertPtr, * p;if (i<1 || i>L->length + 1){printf("非法插入");exit(0);}	//非法插入if (L->length >= L->listsize){base = (ElemType*)realloc(L->elem, (L->listsize + 10) * sizeof(ElemType));//重新追加空間L->elem = base;		//更新內存基地址L->listsize = L->listsize + 100;		//存儲空間增大100單元}insertPtr = &(L->elem[i - 1]);		//insertPtr為插入位置for (p = &(L->elem[L->length - 1]);p >= insertPtr;p--)*(p + 1) = *p;						//將i-1以后的元素順序往后移動一個元素位置*insertPtr = item;					//在第i個位置插入元素L->length++;
}
/*
L：Sqlist類型指針
i：刪除元素的位置
*/
void DelElem(Sqlist* L, int i)
{ElemType* delItem, * q;if (i<1 || i>L->length){printf("非法刪除");exit(0);}delItem = &(L->elem[i - 1]);	//delItem指向表中第i個元素q = L->elem + L->length - 1;			//q指向表尾for (++delItem;delItem <= q;++delItem)*(delItem - 1) = *delItem;		//將第i位置以后的元素依次前移L->length--;				//表長-1
}
void print_list(Sqlist *L)
{int i = 0;for (i = 0;i < L->length;i++)printf("%d  ",L->elem[i]);
}
//測試函數
int main()
{Sqlist L;int i = 0;initSqlist(&L);for (i = 0;i < 15;i++)InsertElem(&L,i+1,i+1);     //每次在末尾插入一個元素printf("\n the content of list is \n");print_list(&L);DelElem(&L, 5);printf("\n the content of list after delete is \n");print_list(&L);_getche();return 0;
}