線性表
線性表的概念
線性表：線性表是最常用且最簡單的以重?cái)?shù)據(jù)結(jié)構(gòu)，是n個(gè)數(shù)據(jù)元素的的有序序列。
線性結(jié)構(gòu)的特點(diǎn)：在非空線性結(jié)構(gòu)表中，
- 存在唯一的一個(gè)被稱為“第一個(gè)”的結(jié)點(diǎn)空闲。
- 存在唯一的一個(gè)被稱為“最后一個(gè)”的結(jié)點(diǎn)。
- 除第一個(gè)之外走敌，表中的每個(gè)結(jié)點(diǎn)均只有一個(gè)前驅(qū)結(jié)點(diǎn)碴倾。
- 除最后一個(gè)之外，表中的每個(gè)結(jié)點(diǎn)均只有一個(gè)后繼結(jié)點(diǎn)掉丽。
空表：線性表中元素n的個(gè)數(shù)為0影斑，即n=0.
線性表的順序存儲(chǔ)結(jié)構(gòu)（C語言）
#include<stdio.h>
#include<malloc.h>
#define OK 1
#define ERROR 0
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define ElemType int
typedef int Status;
typedef struct
{
int *elem;
int length;
int listsize;
}SqList;
//構(gòu)造一個(gè)空的線性表L
//該線性表預(yù)定義大小為LIST_INIT_SIZE
Status InitList_Sq(SqList &L)
{
L.elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if (!L.elem) return OK; // 存儲(chǔ)分配失敗
L.length = 0; // 空表長度為0
L.listsize = LIST_INIT_SIZE; // 初始存儲(chǔ)容量
return OK;
}
//銷毀線性表L
//銷毀成功返回OK
Status DestroyList_Sq(SqList &L)
{
if(L.elem)
{
free(L.elem);
return OK;
}
else return ERROR;
}
//清除線性表L，重置為空表
Status ClearList_Sq(SqList &L)
{
if(!L.elem) return ERROR; //線性表不存在
L.length = 0; //記錄表長（空表）
return OK;
}
Status ListLength(SqList &L)
{
return L.length;
}
Status GetElem(SqList &L,int i,ElemType &e)
{
if(i<L.length) return ERROR;
e = L.elem[i];
return OK;
}
//若cur_e是L的數(shù)據(jù)元素机打，且不是第一個(gè)矫户，則用pre_e返回它的前驅(qū)。
Status PriorElem(SqList &L,ElemType cur_e,ElemType &pre_e)
{
int i = 0;
while(L.elem[i] != cur_e && i<L.length) {i++;}
if(i<L.length)
{
pre_e = L.elem[i-1];
return OK;
}
else return ERROR;
}
// 在順序線性表L的第i個(gè)元素之前插入新的元素e残邀，
// i的合法值為1≤i≤ListLength_Sq(L)+1
Status ListInsert_Sq(SqList &L, int i, ElemType e)
{
ElemType *p;
if (i < 1 || i > L.length+1) return ERROR; // i值不合法
if (L.length >= L.listsize) // 當(dāng)前存儲(chǔ)空間已滿皆辽，增加容量
{
ElemType *newbase = (ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof (ElemType));
if (!newbase) return ERROR; // 存儲(chǔ)分配失敗
L.elem = newbase; // 新基址
L.listsize += LISTINCREMENT; // 增加存儲(chǔ)容量
}
ElemType *q = &(L.elem[i-1]); // q為插入位置
for (p = &(L.elem[L.length-1]); p>=q; --p)
*(p+1) = *p; // 插入位置及之后的元素右移
*q = e; // 插入e
++L.length; // 表長增1
return OK;
}
//在順序線性表L中刪除第i個(gè)元素，并用e返回其值芥挣。
//i的合法值為1≤i≤ListLength_Sq(L)驱闷。
Status ListDelete_Sq(SqList &L, int i, ElemType &e)
{
ElemType *p, *q;
if (i<1 || i>L.length) return ERROR; // i值不合法
p = &(L.elem[i-1]); // p為被刪除元素的位置
e = *p; // 被刪除元素的值賦給e
q = L.elem+L.length-1; // 表尾元素的位置
for (++p; p<=q; ++p) *(p-1) = *p; // 被刪除元素之后的元素左移
--L.length; // 表長減1
return OK;
}
// 輸出順序表中的所有元素
int Load_Sq(SqList &L)
{
int i;
if(L.length == 0) printf("The List is empty!");
else
{
printf("The List is: ");
for(int i=1;i<L.length+1;i++) printf("%d ",L.elem[i-1]);
}
printf("\n");
return OK;
}
int main()
{
SqList T;
int a, i;
ElemType e, x;
if(InitList_Sq(T)) // 判斷順序表是否創(chuàng)建成功
{
printf("順序表創(chuàng)建成功\n");
}
while(1)
{
printf("1:插入數(shù)值\n2:刪除數(shù)值\n3:打印所有數(shù)值\n");
printf("4:輸出特定位置的數(shù)值\n");
printf("5:輸出特定數(shù)值之前的數(shù)值\n");
printf("6:輸出順序表長\n");
printf("7:清空表\n");
printf("0:退出\n請(qǐng)選擇:\n");
scanf("%d",&a);
switch(a)
{
case 1: scanf("%d%d",&i,&x);
if(!ListInsert_Sq(T,i,x)) printf("插入失敗!\n"); // 判斷i值是否合法，請(qǐng)?zhí)羁? else printf("數(shù)值 %d 已經(jīng)被成功插入!\n", x);
break;
case 2: scanf("%d",&i);
if(!ListDelete_Sq(T,i,e)) printf("刪除失敗!\n"); // 判斷i值是否合法空免，請(qǐng)?zhí)羁? else printf("數(shù)值 %d 已經(jīng)被成功刪除!\n", e);
break;
case 3: Load_Sq(T);
break;
case 4: scanf("%d",&i);
if(!GetElem(T, i, e)) printf("獲取失敗!\n");
else printf("第 %d 個(gè)數(shù)值是 %d!\n", i, e);
break;
case 5: scanf("%d",&i);
if(!PriorElem(T, i, e)) printf("無法找到!\n");
else printf("%d 前面是 %d\n",i,e);
break;
case 6: printf("表長是%d\n",ListLength(T));
break;
case 7: ClearList_Sq(T);
break;
case 0: return 1;
}
}
return 0;
}
