《數(shù)據(jù)結(jié)構(gòu)（C語言版）》順序線性表的實現(xiàn)
清華大學(xué)計算機系列教材? ?累計發(fā)行超400萬冊
嚴(yán)蔚敏 吳偉明 編著
數(shù)據(jù)結(jié)構(gòu)（C語言版）
以下是本人對該紫皮書第二章線性表中順序表的代碼實現(xiàn)，函數(shù)部分與課本基本相同
（貌似專欄把我縮進吃了，懶得加了，另外建議用visual studio編譯）
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
typedef int ElemType;
typedef struct?
{
ElemType* elem;//存儲空間基址
int length;//當(dāng)前長度
int listsize;//最大長度
}SqList;
int InitList_sq(SqList& L);//構(gòu)造一個空的線性表L
int ListInsert_Sq(SqList& L, int i, ElemType e);//在順序線性表L中第i個位置之前插入新的元素e
int ListDelete_Sq(SqList& L, int i, ElemType& e);//在順序線性表L中刪除第i個元素，并返回這個元素的值e
int LocateElem_Sq(SqList L, ElemType e, int (*compare)(ElemType, ElemType));//查找第一個與e滿足compare（）的元素的位置
void MergeList_Sq(SqList La, SqList Lb, SqList& Lc);//已知順序線性表La和Lb的元素按值遞增排列，歸并獲得同樣遞增排列的線性表Lc
void Output_Sq(SqList L);//打印線性表中所有元素的值
int compareEqual(int a, int b);
int compareBig(int a, int b);
int compareSmall(int a, int b);
void Menu()
{
printf("*****************************\n");
printf("*********開 始 菜 單*********\n");
printf("*********0：退出系統(tǒng)*********\n");
printf("*********1：插入元素*********\n");
printf("*********2：刪除元素*********\n");
printf("*********3：查找元素*********\n");
printf("*********4：打印表單*********\n");
printf("*****************************\n");
}
int main()
{
SqList MySqList;
int input=0;
int position = 1;
int ret = 0;
int value = 0;
int relation = 1;
InitList_sq(MySqList);
do?
{
Menu();
scanf("%d", &input);
if (input < 0 || input > 4)
{
printf("輸入錯誤，請重新輸入\n");
input = 0;
}
else
{
switch (input)
{
case 1:
printf("請輸入你想插入的位置:");
scanf("%d", &position);
printf("請輸入你想插入的值：");
scanf("%d", &value);
ret = ListInsert_Sq(MySqList, position, value);
if (!ret)
{
printf("插入失敗，請重試\n");
}
else
{
printf("插入成功\n");
}
break;
case 2:
printf("請輸入你想刪除的位置:");
scanf("%d", &position);
ret = ListDelete_Sq(MySqList, position, value);
if (!ret)
{
printf("刪除失敗，請重試\n");
}
else
{
printf("刪除成功，您刪除的值為%d\n", value);
}
break;
case 3:
printf("請輸入你想查找的元素：");
scanf("%d", &value);
printf("請輸入你想查找的關(guān)系：\n");
printf("查找線性表中第一個與其等的元素請按1\n");
printf("查找線性表中第一個比它大的元素請按2\n");
printf("查找線性表中第一個比它小的元素請按3\n");
scanf("%d", &relation);
switch (relation)
{
case 1:
ret = LocateElem_Sq(MySqList, value, compareEqual);
if (!ret)
{
printf("未找到\n");
}
else
{
printf("滿足條件的元素所在的位置為%d\n", ret);
}
break;
case 2:
ret = LocateElem_Sq(MySqList, value, compareBig);
if (!ret)
{
printf("未找到\n");
}
else
{
printf("滿足條件的元素所在的位置為%d\n", ret);
}
break;
case 3:
ret = LocateElem_Sq(MySqList, value, compareSmall);
if (!ret)
{
printf("未找到\n");
}
else
{
printf("滿足條件的元素所在的位置為%d\n", ret);
}
break;
default:
printf("你輸入的值有誤");
break;
}
break;
case 4:
Output_Sq(MySqList);
printf("\n");
break;
case 0:
exit(0);
break;
default:
printf("你輸入的值有誤，請重新輸入");
break;
}
}
} while (input);
//歸并線性表函數(shù)測試
/*SqList MySqList1;
SqList MySqList2;
SqList MySqList3;
InitList_sq(MySqList1);
InitList_sq(MySqList2);
InitList_sq(MySqList3);
ListInsert_Sq(MySqList1, 1, 12);
ListInsert_Sq(MySqList1, 2, 14);
ListInsert_Sq(MySqList1, 3, 18);
ListInsert_Sq(MySqList1, 4, 32);
ListInsert_Sq(MySqList2, 1, 1);
ListInsert_Sq(MySqList2, 2, 2);
ListInsert_Sq(MySqList2, 3, 5);
ListInsert_Sq(MySqList2, 4, 69);
ListInsert_Sq(MySqList2, 5, 70);
ListInsert_Sq(MySqList2, 6, 81);
MergeList_Sq(MySqList1, MySqList2, MySqList3);
Output_Sq(MySqList3);*/
return 0;
}
int InitList_sq(SqList& L)//構(gòu)造一個空的線性表L
{
L.elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType));
if (!L.elem)
{
exit(OVERFLOW);
}
L.length = 0;
L.listsize = LIST_INIT_SIZE;
return OK;
}
int ListInsert_Sq(SqList& L, int i, ElemType e)//在順序線性表L中第i個位置之前插入新的元素e
{
//判斷插入位置是否合法
if (i<1 || i>L.length + 1)//注意要+1
{
return ERROR;
}
if (L.length >= L.listsize)//如果存儲空間滿了用realloc增加分配
{
//關(guān)于realloc函數(shù)的注釋：
//成功分配內(nèi)存后L.elem將被系統(tǒng)回收，一定不可再對L.elem指針做任何操作，包括 free()；相反的，可以對 realloc()函數(shù)的返回值newbase進行正常操作。
//如果是擴大內(nèi)存操作會把L.elem指向的內(nèi)存中的數(shù)據(jù)復(fù)制到新地址（新地址也可能會和原地址相同，但依舊不能對原指針進行任何操作）；如果是縮小內(nèi)存操作，原始據(jù)會被復(fù)制并截取新長度。
ElemType* newbase = (ElemType*)realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(ElemType));
if (!newbase)
{
exit(OVERFLOW);
}
L.elem = newbase;
L.listsize += LISTINCREMENT;
}
int* q = &L.elem[i - 1];//q為插入位置，注意要減一
for (int* p = &L.elem[L.length - 1]; p >= q; p--)
{
*(p + 1) = *p;
}
*q = e;
L.length++;//更新表長
return OK;
}
int ListDelete_Sq(SqList& L, int i, ElemType& e)//在順序線性表L中刪除第i個元素，并返回這個元素的值e
{
//判斷刪除位置是否合法
if (i<1 || i>L.length)
{
return ERROR;
}
int* p = &L.elem[i - 1];//p為刪除位置，注意要減一
e = *p;//用e保存被刪去元素的值
int* q = L.elem + L.length - 1;//q為表尾位置
for (p++; p <= q; p++)
{
*(p - 1) = *p;
}
L.length--;//更新表長
return OK;
}
int LocateElem_Sq(SqList L, ElemType e, int (*compare)(ElemType, ElemType))//查找第一個與e滿足compare（）的元素的位置
{
int i = 1;
int* p = L.elem;
while (i <= L.length && !(*compare)(*p++, e))
{
i++;
}
if (i <= L.length)
{
return i;
}
else
{
return 0;
}
}
int compareEqual(int a, int b)
{
if (a == b)
{
return 1;
}
else
{
return 0;
}
}
int compareBig(int a, int b)
{
if (a > b)
{
return 1;
}
else
{
return 0;
}
}
int compareSmall(int a, int b)
{
if (a < b)
{
return 1;
}
else
{
return 0;
}
}
void Output_Sq(SqList L)//打印線性表中所有元素的值
{
if (L.length == 0)
{
printf("空表");
}
else
{
for (int i = 0; i < L.length; i++)
{
printf("%d ", *(L.elem + i));
}
}
}
void MergeList_Sq(SqList La, SqList Lb, SqList& Lc)//已知順序線性表La和Lb的元素按值遞增排列，歸并獲得同樣遞增排列的線性表Lc
{
int* pa = La.elem;
int* pb = Lb.elem;
Lc.length = La.length + Lb.length;
Lc.listsize = Lc.length;
Lc.elem = (ElemType*)malloc(Lc.listsize * sizeof(ElemType));
if (!Lc.elem)
{
exit(OVERFLOW);
}
int* pc = Lc.elem;
int* pa_last = La.elem + La.length - 1;
int* pb_last = Lb.elem + Lb.length - 1;
while (pa <= pa_last && pb <= pb_last)
{
if (*pa <= *pb)
{
*pc++ = *pa++;
}
else
{
*pc++ = *pb++;
}
}
while (pa <= pa_last)//如果表a或表b有剩余元素則全部添加到表c后面
{
*pc++ = *pa++;
}
while (pb <= pb_last)
{
*pc++ = *pb++;
}
}
