前言

本篇介紹資料結構中存盤元素–線性表中的順序表

線性表

線性表（linear list）是n個具有相同特性的資料元素的有限序列， 線性表是一種在實際中廣泛使用的資料結構，常見的線性表：順序表、鏈表、堆疊、佇列、字串…

線性表在邏輯上是線性結構，也就說是連續的一條直線，但是在物理結構上并不一定是連續的，線性表在物理上存盤時，通常以陣列和鏈式結構的形式存盤

順序表

• 順序表是用一段物理地址連續的存盤單元依次存盤資料元素的線性結構，一般情況下采用陣列存盤，在陣列上完成資料的增刪查改

• 靜態和動態順序表

• 靜態順序—使用定長陣列存盤元素

• 動態順序表—動態存盤元素

  

• 靜動態比較

靜態順序表只適用于確定知道需要存多少資料的場景，靜態順序表的定長陣列導致N定大了，空間開多了浪
費，開少了不夠用，所以現實中基本都是使用動態順序表，根據需要動態的分配空間大小，所以下面我們實
現動態順序表

動態順序表

結構體宣告

既然動態存盤元素，自然需要先確定一個當前開辟記憶體的最大容量–capacity和記錄有效資料個資料的指標，方便進行記憶體的訪問，因此定義結構體：

typedef  int  SLDateType;//方便修改順序表的元素型別

typedef struct SeqList//重命名結構體為SL
{

	SLDateType* psl;//psl指向動態申請的空間.
	size_t sz;//記錄有效資料個數
	size_t capacity;//開辟空間的容量
}SL;

初始化結構體

• 陣列下標是從0開始的，因此初始化中的sz，總是指向陣列中下一個元素的下標，這很特殊！！！！后面判斷當前申請的空間是否滿要留意，

void SeqListInit(SL* p)
{
	assert(p);
	p->psl = NULL;
	p->sz = 0;
	p->capacity = 0;
}

判斷陣列是否滿

• 假設陣列最大容量是10，因此陣列下標從0開始，因此當sz等于cappacity時就滿了，

void SeqListRealloc(SL* p)
{

	if (p->sz == p->capacity)//當相等時，就需要擴容了，這里我以二賠擴容.
	{
		p->capacity = p->capacity == 0 ? 4 : 2 * p->capacity;
		SLDateType* tmp = (SLDateType*)realloc(p->psl, p->capacity * sizeof(SLDateType));
		if (tmp == NULL)
		{
			printf("");
			exit(-1);
		}
		p->psl = tmp;
	}
}

指定位置，插入元素

• 頭插，尾插只是其中的一種形式，后面可以復用SeqListInsert

• 注意陣列下標

void SeqListInsert(SL* p, size_t pos, SLDateType x)//在指定位置pos，插入元素，
{
	 
	assert(p);
	assert(pos <= p->sz  && pos>=0);//順序表是依次填入資料的，因此不能比較capacity
	SeqListRealloc(p);//判斷是否需要擴容，
	for (size_t  i = p->sz; i>pos; --i)//size_t 要考慮
	{

		p->psl[i] = p->psl[i-1];
	
	}
	p->psl[pos] = x;
	p->sz++;
}

頭插元素

void SeqListPushFront(SL* p, SLDateType x)//頭插元素.
{
	assert(p);
	SeqListInsert(p, 0, x);

}

尾插元素

void SeqListPushBack(SL* p, SLDateType x)//尾插元素.
{
	assert(p);
	SeqListInsert(p, p->sz, x);
}

指定位置刪元素

• 注意我們指的洗掉元素，并不是真的洗掉它，而是通過sz–的形式，因為一方面當后續添加元素時，在相應位置添加元素就行，另外一方面是動態開辟的記憶體不允許在中間就行釋放動態記憶體，

void SeqListErase(SL* p, size_t pos)//指定位置pos(代表陣列下標)洗掉.
{
	assert(p);
	assert(pos <= p->sz && pos >= 0);
	for (size_t i = pos; i < p->sz - 1; ++i)
	{
		p->psl[i] = p->psl[i + 1];
	}
	p->sz--;
}

頭刪元素

void SeqListPopFront(SL* p)//頭刪元素.
{

	assert(p);
	SeqListErase(p, 0);
}

尾刪元素

void SeqListPopBack(SL* p)//尾刪元素.
{
	assert(p);
	SeqListErase(p, p->sz-1);

}

查找元素

int SeqListFind(SL* p, SLDateType x)//在查找元素，找到回傳下標，否則0； 
{
   
   
  
	for (size_t i = 0; i < p->sz; ++i)
	{
		if (x == p->psl[i])
		{
			return i;
		}
	}

	return 0;
}

列印陣列

void SeqListPrint(SL* p)//列印
{
	assert(p);
	for (size_t i = 0; i < p->sz; ++i)
	{
		printf("%d  ", p->psl[i]);
	}
	printf("\n");
}

銷毀申請的空間

void SeqLIstDestory(SL* p)//free
{
	free(p->psl);
	p->psl = NULL;
	p->capacity = 0;
	p->sz = 0;

}

選單

// 構建動態順序表，
enum whole
{
	Exit,
	pushfront,
	pushback,
	pushinsert,
	popfront,
	popback,
	poperase,
	popdate,
	print
};
void menu()
{

	printf("************************************************************\n");
	printf("***************靜態順序表***********************************\n");
	printf("*********1.頭插        2.尾插  3.任意位置插*****************\n");
	printf("*********4.頭刪        5.尾刪  6.任意位置刪*****************\n");
	printf("*********7.指定元素刪  8.列印  0 .Exit  ********************\n");
	printf("************************************************************\n");

}

int main ()
{
	SL s;
	
	int input = 0;
	SeqListInit(&s);
	SLDateType x = 0;//要是你是整型，需修改scanf.
	int Flage = 0;
	size_t pos = 0;//位置
	int ret = 0;
	do
	{
		menu();
		printf("請輸入你的選擇:");
		scanf("%d", &input);
		switch (input)
		{
		
		case pushfront:	
			printf("\t頭插\n");
			printf("請輸入你要插入的元素->,以0為結束標志\n");
			scanf("%d", &x);
			while (x)
			{
				SeqListPushFront(&s, x);
				scanf("%d", &x);

			}
		    break;

		case pushback:	
			printf("\t尾插\n");
			printf("請輸入你要插入的元素->,以0為結束標志\n");
			scanf("%d", &x);
			while (x)
			{
				SeqListPushBack(&s, x);
				scanf("%d", &x);
			}
			break;
		case pushinsert:
			printf("\t任意位置插\n");
			printf("請輸入你要插入的元素->與位置->,以0為結束標志\n");
			scanf("%d%d", &x,&pos);
			while (x)
			{
				SeqListInsert(&s,pos, x);
				scanf("%d%d", &x,&pos);
			}
			break;
			 
		case popfront:
			printf("\t頭刪\n");
			printf("輸入一個數，以非0數表示進行頭刪，0表示結束\n");
			scanf("%d", &Flage);
			while (Flage)
			{
				SeqListPopFront(&s);
				scanf("%d", &Flage);
			}
			break;


		case popback:
			printf("\t尾刪\n");
			printf("輸入一個數，以非0數表示進行尾刪，0表示結束\n");
			scanf("%d", &Flage);
			while (Flage)
			{
				SeqListPopBack(&s);
				scanf("%d", &Flage);
			}
			break;
		case poperase:
			printf("\t任意位置刪\n");
			printf("請輸入一個數，以1表示進行任意位置洗掉,以0為結束標志，并輸入一個位置\n");
			scanf("%d%d", &Flage,&pos);
			while (Flage)
			{
				SeqListErase(&s,pos);
				scanf("%d%d", &Flage, &pos);

			}
			break;
		case popdate:
			printf("\t指定元素洗掉\n");
			printf("輸入一個數，以非0數表示進行頭刪，0表示結束,并輸入指定元素\n");
			scanf("%d%d", &Flage, &x);
			while (Flage)
			{
				ret = SeqListFind(&s, x);
				if (ret != -1)
				{
					SeqListErase(&s, ret);
					printf("洗掉成功\n");
				}
				else
				{
					printf("該資料不存在\n");
				
				}
				scanf("%d%d", &Flage, &x);
			}
			break;
		case print:
			SeqListPrint(&s);
			break;
		case Exit:
			SeqLIstDestory(&s); 
			system("cls");
			printf("感謝使用!\n");
			break;
		default:printf("輸入有誤，請重新輸入");

		}

	} while (input);

	return 0;
}

效果展示

總結

• 搞這些是為了熟悉動態順序表，另外程式中得選單是不需要特別去在意，能把代碼功能無BUG的搞出來，才是對的，
• 下面介紹順序表中的鏈表—8種鏈表形式，主要用其中2種，