数据结构——链表总结
单链表操作
Status 是函数的类型，其值是函数结果状态代码
typedef int Status
//函数结果状态代码
#define True 1
#define False 0
#define OK 1;
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
1.单链表的定义和表示
typedef struct {
char name[10];
char num[20];
double score;
}Stu;
typedef struct LNode {
Stu data;
struct LNode *next;
}LNode,*LinkList;
2.初始化链表（带头结点的单链表）
思路：
- 生成新结点作头结点，用头指针L指向头结点
- 头结点的指针域置空
Status InitList_L(LinkList L)
{
L = (LinkList)mallloc(sizeof(LNode));
L->next = NULL;
return OK;
}
3.判断链表是否为空
空表：链表中无元素（头指针和头结点仍然存在）
思路：判断头结点指针域是否为空
Status ListEmpty(LinkList L) { if(L->netx) return 0; else return 1; }
4.销毁单链表
思路：从头指针开始，依次释放所有结点
Status DestroyList_L(LinkList L)
{
LNode *p; //或者 LinkList p;
while(L)
{
p=L;
L=L->next;
free p;
}
}
5.清空单链表
思路：依次释放所有结点，并为头结点指针域设置为空
Status ClearList(LinkList L)
{
LNode *p,*q;
p=L->next;
while(p)
{
q = p->next;
free p;
p = q;
}
L->next = NULL; //头结点指针域为空
return OK;
}
6.求单链表长度
思路：从首元结点开始，依次计数所有结点
Status ListLength_L(LinkList L)
{
LNode *p;
p = L->next; //p指向第一个结点
int i = 0;
while(p) //遍历单链表，统计结点数
{
i++;
p = p->next;
}
return i;
}
7.取值
Status GetElem_L(LinkList L, int i, ElemType e)
{
LinkList p = L->next;
int j = 1; //p指向第一个结点,j做计数器，累计当前扫描过的结点数
while(p && j<i) //向后扫描，p指向第i个元素或者p为空
{
p = p->next;
j++;
}
if (!p || j>i) //第i个元素不存在
return ERROR;
e = p->data; //取第i个元素
return Ok;
}
8.按值查找
Status LocatElem_L(LinkList L,Elemtype e)
{
LinkList p = L->next;
int j = 1;
while(p && p->data != e)
{
p = p->next; //遍历
j++; //位置序号
}
if(p)
return i;
else
return 0;
}
9.插入值
思路：
- 想要在链表第 i 个元素前面插入新结点，则需要将指针指向第 i-1 个元素，从而将其 next 域中保存的第 i 个元素地址赋值给新结点，实现链接
LinkList p = L;
int j = 0;
while(p && j<i-1)
代码中创建了指向头结点的指针变量，初始化起点并非首元结点，所以要想在第 i 个位置插入，while 循环次数需为 i-1
若初始化为首元结点，即
LinkList p = L->next;
则 while 循环次数为 i-2，从而根据循环次数要求去初始化 j 或改变循环结束的条件
Status ListInsert_L(LinkList L, int i, Elemtype e)
{
LinkList p = L;
int j = 0;
while(p && j<i-1)
{
p = p->next;
++j;
}
if(!p || j>i-1)
return ERROR;
s = (LinkList)malloc(sizeof(LNode));
s->data = e;
s->next = p->next;
p->next = s;
return Ok;
}
10. 删除第 i 个结点
Status ListDelete_L(LinkList_L, int i, Elemtype e)
{
LinkList p = L;
LinkList q;
int 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;
}
单链表的创建
1. 头插法(前插法）
思路：
- 从一个空表L开始，重复读入数据；
- 生成新结点，将读入数据存放到新结点的数据域中
- 从最后一个结点开始，依次将各结点插入到链表的前端
void CreatList_H(LinkList L, int n)
{
L = (LinkList)malloc(sizeof(LNode));
L->next = NULL; //建立一个带头结点的单链表
for(i=n; i>0; --i)
{
p = (LinkList)malloc(sizeof(LNode)); //生成新结点p
scanf(&p->data); //获取输入值
p->next = L->next; //插入到表头
L->next = p;
}
}
2. 尾插法(后插法)
思路：
- 从一个空表L开始，将新结点逐个插入到链表的尾部，尾指针 r 指向链表的尾结点
- 初始时，r 同 L 均指向头结点。每读入一个数据元素则申请一个新结点，将新结点插入到尾结点后，r 指向新结点
void CreatList(LinkList L, int n)
{
L = (LinkList)malloc(sizeof(LNode));
L->next = NULL;
LNode *r;
r = L; //尾指针 r 指向头结点
for(i=0; i<n; i++)
{
p = (LinkList)malloc(sizeof(LNode)); //生成新结点，输入元素值
scanf(&p->data);
p->next = NULL;
r->next = p; //插入到表尾
r = p; //r 指向新的尾结点
}
}
循环链表
1.创建
//先创建初始化结点函数
LinkList initlist()
{
LNode *head = (LinkList)malloc(sizeof(LNode));
if(head == NULL)
{
printf("创建失败，退出程序");
}
else
{
head->next = NULL;
return head;
}
}
//创建循环链表
Status Insert_List(LNode *head)
{
int data;
printf("输入插入的元素：");
scanf("%d",&data);
LinkList node = initlist();
node->data = data; //初始化新结点
if(head != NULL)
{
LNode *p = head;
while(p->next != head) //找到最后一个元素
{
p = p->next;
}
p->next = node;
node->next = head;
return 1;
}
else
{
printf("头结点已无元素\n");
return 0;
}
}
2. 带尾指针循环链表合并
LinkList Connect(LinkList Ta, LinkList Tb)
{ //假设Ta，Tb都是非空的单循环链表
p = Ta->netx; //p 存表头结点
Ta->next = Tb->next->next; //Tb 表头连接 Ta 表尾
free Tb->next; //释放 Tb 表头结点
Tb->next = p; //修改指针
return Yb;
}//时间复杂度O(1)
双向链表
1. 创建
//结点创建
typedef struct DuLNode
{
Elemtype data; //data
struct DuLNode *pre; //前驱 node
struct DuLNode *next; //后继 node
}DuLNode,*DuLinkList;
//插入数据
Status ListInsert_DuL(DuLinkList L, int i, ElemType e)
{
//在带头结点的双链循环线性表L中第i个位置之前插入元素e
//i的合法值为 1<=i<=表长+1
if(!(p = GetElemP_DuL(L,i))) //在L中确定插入的位置
return ERROR; //p=NULL,即插入位置不合法
if(!(s=(DuLinkList)malloc(sizeof(DuLNode))))
return ERROR;
s->data = e;
s->prior = p->prior; p->prior->next = s;
s->next = p; p->prior = s;
return OK;
}//LinkInsert_DuL
2.删除
Status ListDelete_DuL(DuLinkList L, int i, ElemType e)
{
//删除带头结点的双链循环线性表L的第i个元素，i的合法值为1<=i<=表长
if(!(p = GetElemP_DuL(L,i))) //在L中确定第i个元素的位置指针p
return ERROR;
e = p->data;
p->prior->next = p->next;
p->next->prior = p->prior;
free(p);
return OK;
}ListDelete_DuL
--> 单链表操作Status 是函数的类型，其值是函数结果状态代码typedef int Status//函数结果状态代码#define True 1#define False 0#define OK 1;#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2 1.单链表的定义和表示typedef struct { c...