线性表的类型定义
- 线性表:具有相同特性数据元素的一个有限序列
在复杂的线性表中，一个数据元素由若干个数据项组成。在这种情况下，常把数据元素称为记录，含有大量记录的线性表又称为文件
- 结构特点:存在唯一的一个被称做“第一个”的数据元素;除第一个元素外，集合中的每个元素均只有一个前驱;除最后一个之外，集合中每个元素均只有一个后继。
- 存储结构:顺序表和链表
- 顺序表:做插入操作需要移动多个元素，随机访问特性，存储空间静态分配，存储密度=1
- 顺序表:做插入操作需要移动多个元素，随机访问特性，存储空间静态分配，存储密度=1
- 链表:插入操作不需要移动元素，存储空间动态分配，顺序存取，存储密度＜1
线性表的基本操作
顺序表
用一组地址连续的存储单元依次存储线性表的数据元素
- 静态分配
#define maxleng 100
typedef struct{
ElemType elem[maxleng]
int length //表长
}SqList
// L. elem[i-1]之前插入新元素e，(1<=i<=length+1)
int Insertl (SqList *L, int i,ElemType e){
if (i<1|| i>L->length+1) return ERROR; //i值不合法
if (L->1ength>=max leng) return OVERFLOW; //溢出
for (j=L->length-l; j>=i-l; j--)
L->elem[j+1]-L->elem[j];//向后移动元素
L->elem[i-I]=e;//插入新元素
L->length++;//长度变量增1
return 0K ; //插入成功
}//
- 动态分配
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
typedef strut{
Elemtype *elem //存储空间基地址
int length //当前长度
int listsize //当前分配的存储容量(以sizeof(Elemtype)为单位)
}SqList
//L. elem[i-1]之前插入新元素e，(1<=i<=length+1)
int Insert2(SqList &L, int i, ElemType e){
if (i<1|| i>L.length+1) return ERROR; //i值不合法
if (L->1ength>=L.listsize){
newbase = (Elemtype*)realloc(l.listsize+LISTINCREMENT)*sizeof(eleElemtype);
if(！newbase)exit(OVERFLOW);//存储分配失败
L.elem = newbase;//新基地址
L.listsize += LISTINCREMENT;
} //当前存储空间已满，增加分配
q = &(L.elem[i-1]);
for (p=L.elem[L.length-1]; p>=q; --p) *(p+1) = *p;//插入位置及之后的元素后移
*q = e;
++L.length;
return OK;
}Insert2
Status Delete(Sq_list &L,int i,Elemtype &e){
//在顺序表中删除第i个元素，并返回e值
if((i<1||i>Length)) return ERROR;
p = &（L.elem[i-1]）;//为被删除元素的位置
e = *p;//被删除的元素赋值给e
q = L.elem+L.length-1;//表尾元素的位置
for（++p; p <= q;++p） *（p-1）=*p;被删除元素之后的元素左移
--L.length;//表长-1
return OK;
}
插入元素平均移动次数:n/2
删除元素平均移动次数:n-1/2
时间复杂度O（n）
链表
它包括两个域:数据域和指针域
单链表
-
不带表头节点的单链表enter image description here
其中：data为数据域，next为指针域。当head == NULL，为空表；否则为非空表
-
带表头节点的单链表enter image description here
其中：head指向表头节点，head->data不放元素，head->next指向首结点a1，当head->next == NULL，为空表，否则为空表。
//结点和单链表的c语言描述
Typedef struct LNode {
ElemType data; //数据域
struct Lnode *next; //指针域
}LNode, *LinkList;
...
LinkList L； // L为单链表的头指针
-
生成单链表
（1）先进先出单链表（链式队列）
enter image description here
struct node *creat1( )
{ struct node *head, *tail, *p;//变量说明
int e;
head= (struct node *) malloc (LENG); //生成表头结点
tail =head; //尾指针指向表头
scanf ("%d", &e) ; //输入第一个数
while (e!=0) {
p= (struct node *) malloc (LENG); //生成新结点
p->data=e; //装入输入的元素e
tail- >next=p; //新结点链接到表
tail=p; //尾指针指向新结
scanf (“%d", &e);
}
tail -> next = NULL; //尾结点的next置为空指针
return head; //返回头指针
}
(2)生成后进先出单链表(链式队列)
enter image description here
struct node *creat2( )
{ struct node *head, *tail, *p;//变量说明
int e;
head= (struct node *) malloc (LENG); //生成表头结点
head -> = NULL;//置为空表
scanf ("%d", &e) ; //输入第一个数
while (e!=0) {
p= (struct node *) malloc (LENG); //生成新结点
p->data=e; //装入输入的元素e
head ->next = head->next; //新结点指针指向原来的首结点
head ->next = p; //新结点作为首元素
scanf (“%d", &e);
}
return head;//返回头指针
}
-
插入一个结点enter image description here
注意：若要在第 i 个结点之前插入元素，修改的是第 i-1 个结点的指针。
Status ListInsert_L(LinkList L, int i, ElemType e) {
// L 为带头结点的单链表的头指针，本算法
// 在链表中第i 个结点之前插入新的元素 e
p = L; j = 0;
while (p && j < i-1) { // 寻找第 i-1 个结点
p = p->next; ++j;
}
if (!p || j > i-1) return ERROR; // i 大于表长或者小于1
s = (LinkList) malloc ( sizeof (LNode)); // 生成新结点
s->data = e; // 插入，关键!!!
s->next = p->next;
p->next = s;
return OK;
} // LinstInsert_L
3.在单链表中删除一个结点
enter image description here
Status ListDelete_L(LinkList L, int i, ElemType &e) {
// 删除以 L 为头指针(带头结点)的单链表中第 i 个结点
p = L; j = 0;
while (p->next && j < i-1) { //寻找第 i 个结点，并令 p 指向其前趋
p = p->next; ++j;
}
if (!(p->next) || j > i-1) return ERROR; // 删除位置不合理
q = p->next; // 删除并释放结点,关键!!!
p->next = q->next;
e = q->data;
free(q); //注意
return OK;
} //ListDelete_L
