Day 3 - 5 ：线性表

Day 3 - 5 ：线性表 — 单链表

存储结构

将线性表中的各元素分布在存储器的不同存储块，称为结点。

结点的data域存放数据元素ai，而next域是一个指针，指向ai的直接后继ai+1所在的结点。

如果要删除a1，只要修改a1前手元素指针的指向即可。

例如：需要找到带头节点（例如：下图的赵）

节点类型描述

typedef int data_t;
typedef struct node
{data_t data;		//结点的数据域struct node* next;	//结点的后继指针域
}listnode,*linknode;

注意：

若说明：

listnode A;

linknode p = &A;

设p是指向链表中结点ai：

获取ai，写作: p -> data;

获取ai+1，写作:p -> next ->data;

若指针p的值为NULL，则它不指向任何结点, 此时取p->data或p->next是错误的。

基本运算的相关算法

建立单链表

依次读入表L=(a0,.....,an-1)中每一元素ai(假设为整型)，若ai≠结束符（-1），则为ai创建一结点，然后插入表尾，最后返回链表的头结点指针H。

目的：逻辑相邻的，在物理上利用指针达成相邻的结果。

链表的结构是动态形成的，即算法运行前，表结构是不存在的。

整体思路：

1.申请内存

2.赋初值

3.返回头结点的地址

linklist list_create()
{linklist H = malloc(sizeof(listnode));if (H == NULL){printf("malloc failed!\n");}H->data = 0;H->next = NULL;return H;
}

尾部插入

整体思路：

1.建立一个新结点，申请malloc

2.赋值

3.找到尾结点（最后一个节点最大的特征就是，它只有数据域内有信息，指针域里面是空。）

4.尾部插入

来源：数据结构：图文详解单链表的各种操作（头插法，尾插法，任意位置插入，删除节点，查询节点，求链表的长度，清空链表）_单链表的插入-CSDN博客

int list_tail_insert(linklist H, data_t value)
{linklist p;linklist q;if (H == NULL){return -1;}p = malloc(sizeof(listnode));if(p == NULL){printf("malloc failed!\n");return   -1;}p->data = value;p->next = NULL;q = H;while (q->next != NULL){q = q->next;}q->next = p;//把新结点的地址存到尾结点的位置return 0;
}

链表遍历

int list_show(linklist H)
{linklist p;if (H == NULL){return -1;}p = H;while (p->next != NULL){printf("%d ", p->next->data);//注意：跳过了第一个结点p = p->next;}puts('\n');return 0;
}

链表插入

即实现InsertLinklist(h, x, i,)。将x插入表中结点ai之前的情况。

算法思路：调用算法GetLinklist(h, i-1)，获取结点ai-1的指针p(ai 之前驱)，然后申请一个q结点，存入x，并将其插入p指向的结点之后。

注意：这里先后顺序的逻辑来源于查找函数（序号查找）的逻辑。

int list_insert(linklist H, data_t value, int pos)
{linklist q = malloc(sizeof(listnode));if (q == NULL){return -1;}q->data = value;q->next= NULL;linklist p = list_get(H, pos-1);/*因为跳过了第一个结点所以pos-1等于*/if (p == NULL){return -1;}q->next = p->next;p->next = q;linklist k = list_get(H, pos);q->next = k->next;return 0;
}

链表删除

即实现DeleteLinklist(h, i)。

第一步，我们直接更改要删除节点的前面节点的指针域，让它指向要删除的节点后的节点。

第二步，我们将要删除的节点的指针域置为空。

int list_delete(linklist H, int pos)
{if (H == NULL){return -1;}linklist p = list_get(H, pos-1);linklist q;if (p->next == NULL)/*前驱就是最后一个没法删除了*/{return -1;}q = p->next;p->next = q->next;free(q);q = NULL;return 0;
}

链表释放

重新定义一个指针q，保存p指向节点的地址，然后p后移保存下一个节点的地址，然后释放q对应的节点，以此类推，直到p为NULL为止。

注意：p、q属于同一结点，不能先释放空间再让p后移。

注意：程序示范中，H应赋值为NULL，否则在链表释放后仍可以对链表进行操作。

来源：链表基础知识详解（非常详细简单易懂）-CSDN博客

linklist list_free(linklist H)
{linklist p = H;if (H == NULL)return NULL;printf("free\n");while (H != NULL){p = H;H = H->next;free(p);p = NULL;}/*如何使H为NULL*///H = NULL;/*error:H是形参，对H赋值没有意义。*/puts("\n");return NULL;
}

链表查找

1）按序号查找：实现GetLinklist(h, i)运算。

算法思路：从链表的a0起，判断是否为第i结点，若是则返回该结点的指针，否则查找下一结点,依次类推。

linklist list_get(linklist H, int pos)
{if (H == NULL){return NULL;}if (pos == -1)//规定了-1位 = H{return H;}linklist p;p = H;int i = -1;while (i < pos){p = p->next;if (p == NULL)//说明pos超过了链表的范围{return NULL;}i++;}return p;
}

2）按值查找（定位）：即实现Locate(h, x)。

算法思路：从链表结点a0起，依次判断某结点是否等于x,若是，则返回该结点的地址，若不是，则查找下一结点a1,依次类推。若表中不存在x,则返回NULL。

链表复杂操作的实现

链表的倒置

算法思路：依次取原链表中各结点，将其作为新链表首结点插入H结点之后。

【算法】反转链表的四种方法（C语言）_链表反转-CSDN博客

int list_reverse(linklist H)
{linklist p;linklist q;if (H == NULL){return -1;}if (H->next == NULL||H->next->next==NULL)/*空表 or 只有一个节点*/{return -1;}/*从第0个元素开始，把链表一分为二。例如：0 1 2 3 4 -》（0 1）（2 3 4）*/p = H -> next -> next;H -> next -> next = NULL;/*p负责移动指针，q负责把第二个链表-1位插入第一个链表第0位*/while (p != NULL){q = p;p = p->next;q->next = H->next;H->next = q;}return 0;
}

相邻之和求最大值

求链表中相邻两结点data值之和为最大的第一结点的指针。

算法思路：设p,q 分别为链表中相邻两结点指针，求p->data+q->data为最大的那一组值，返回其相应的指针p即可。

linklist list_adjmax(linklist H)
{/*保证节点个数>2,小于2没有任何意义*/if (H -> next ->next->next == NULL){return NULL;}linklist p;linklist q;linklist key = NULL;p = H->next;q = H->next->next;while (q != NULL){int max = 0;if ((p->data + q->data) > max){max = p->data + q->data;key = p;}p = p->next;q = q->next;}return key;
}