线性表是最基本、最简单、也是最常用的一种数据结构。
线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的（注意，这句话只适用大部分线性表，而不是全部。比如，循环链表逻辑层次上也是一种线性表（存储层次上属于链式存储），但是把最后一个数据元素的尾指针指向了首位结点）。
线性表的两种存储方式
- 顺序存储
- 链式存储
线性表的顺序存储
typedef struct LinkedList{
int data[MAXSIZE];//存储数组
int Last;//游标指针
}List;
List * MakeEmpty(){
List *Ptrl;
Ptrl=(List *)malloc(sizeof(List));
Ptrl->Last=-1;
return Ptrl;
}
/**T(n)=O(N)*/
int FindElement(int result,List* Ptrl){
int i=0;
while(i<=Ptrl->Last&&Ptrl->data[i]!=result)
i++;
if(i>Ptrl->Last)return -1;//如果没有找到返回-1
else return i;
}
void Insert(int result,int i,List *Ptrl){
int j;
if(Ptrl->Last==MAXSIZE-1){
printf("表满");
return;
}
if(i<1||i>Ptrl->Last+2){
printf("插入位置不合法");
return;
}
for(j=Ptrl->Last;j>=i-1;j--)//倒序移动（注意j>=i-1）
Ptrl->data[j+1]=Ptrl->data[j];
Ptrl->data[i]=result;//插入数据
Ptrl->Last++;//Last指针++
return;
}
/*T(N)=O(N)*/
void DeleteElement(int i,List* Ptrl){
int j;
if(i<1||i>Ptrl->Last+1){//判断位置的合法性（注：链表下标是从1开始的）
printf("第%d个元素不存在",i);
return;
}
for(j=i;j<=Ptrl->Last;j++)//所有元素前移
Ptrl->data[j-1]=Ptrl->data[j];
Ptrl->Last--;
return;
}
线性表的链式存储
typedef struct LinkedList {
int data;
struct LinkedList *next;
} List;
//求链表长度
int Length(List *Ptrl) {
List *p = Ptrl;
int j = 0;
while (p) {
p = p->next;
j++;
}
return j;
}
//按序号查找
List *FindKth(int k, List *Ptrl) {
List *p = Ptrl;//不改变头节点，返回移动指针p
int i = 1;
while (p != NULL && i < k) {
p = p->next;
i++;
}
if (i == k)return p;
else return NULL;
}
//按值查找
List *Find(int result, List *Ptrl) {
List *p = Ptrl;
while (p != NULL && p->data != result)
p = p->next;
return p;
}
//构造新的结点，申请空间
//找到链表的低i-1个结点
//修改指针插入结点
List *Insert(int result, int i, List *Ptrl) {
List *p, *s;
if (i == 1) {//判断链表为空的时候
s = (List *) malloc(sizeof(List));
s->data = result;
s->next = Ptrl;
return s;
}
p = FindKth(i - 1, Ptrl);//查找第i-1个节点
if (p == NULL) {
printf("参数错误");
return NULL;
} else {
s = (List *) malloc(sizeof(List));
s->data = result;
s->next = p->next;
p->next = s;
return Ptrl;
}
}
List *Delete(int i, List *Ptrl) {
List *p, *s;
if (i == 1) {//检查要删除的是不是第一个结点
s = Ptrl;//s指向第一个结点
if (Ptrl != NULL)Ptrl = Ptrl->next;//从链表中删除
else return NULL;
free(s);//释放空间
return Ptrl;
}
p = FindKth(i, Ptrl);
if (p == NULL) {//后项前移
printf("输入错误");
return NULL;
} else if (p->next != NULL) {
s=p->next;
p->next = s->next;
free(s);//清理无用空间
return Ptrl;
}
}
