2020年考研数据结构复习——单链表

2020年考研数据结构复习——单链表

2020年考研数据结构复习——单链表

代码

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <cstring>
#include "malloc.h"//单链表存储结构
typedef struct LNode
{int data;struct LNode *next;} LNode, *LinkList;//头插法
void CreateList_L(LinkList &L)
{//头插法建立带头节点的链表L->next = NULL;//先建立一个带头节点的单链表int x;scanf("%d", &x); //输入元素值while(x!=-1){LNode *p = (LNode*)malloc(sizeof(LNode));p -> data = x;p -> next = L->next;L->next = p; //插入scanf("%d", &x);}
}void CreateList_L2(LinkList &L)
{//尾插法建立带头节点的链表L->next = NULL;//先建立一个带头节点的单链表LNode *q = L;int x;scanf("%d", &x); //输入元素值while(x!=-1){LNode *p = (LNode*)malloc(sizeof(LNode));p -> data = x;p -> next = NULL;q -> next = p;q = p; //q用于保存最后一个链表节点scanf("%d", &x);}
}//计算链表的长度
int Link_length(LinkList L)
{//计算链表的长度LNode *p = L->next;int length = 0;while(p!=NULL){length++;p = p->next;}return length;
}//取得第i项的值，按位置查找
int GetElem(int i, LinkList L)
{if(i<0&&i>Link_length(L))return -1;//查询位置不合法，返回-1LNode *p = L->next;int l = 1;while(p!=NULL){if(l==i)return p->data;p = p->next;l++;}}
//返回最后一个LNode节点
LNode* lastlnode(LinkList L)
{LNode *p = L;while(p->next!=NULL){p = p->next;}return p;
}//头插法
void insert_head(LinkList &L, int x)
{LNode *p = (LNode*)malloc(sizeof(LNode));if (p==NULL)return;p->data = x;p->next = L->next;//新建节点指向头节点的下一个L->next = p; //p指向头节点后，即将新节点插入链表中
}//尾插法
void insert_tail(LinkList &L, int x)
{LNode *p = (LNode*)malloc(sizeof(LNode));if (p==NULL)return;p->data = x;p->next = NULL;LNode *q = lastlnode(L);q->next = p; //将新节点插入链表中
}//删除指定位置的节点,并返回其值
void delete_head(int i,int &x,LinkList &L)
{if(i<0&&i>Link_length(L))return;//删除位置不合法，返回-1LNode *p = L;LNode *q = L;int l = 0;while(p!=NULL){q = p->next;if(l+1==i)p->next=q->next;x=p->data;free(q);char str[10]="删除成功";printf("%sn",str);return;p = p->next;l++;}
}//转置
void reserve(LinkList &L)
{if(L==NULL||L->next==NULL||L->next->next==NULL)return;LNode *p = L->next;LNode *q = p->next;p->next = NULL; //第一个p相当于最后一个，其指针域指向空LNode *l;while(q->next != NULL){l = q->next;q->next = p;p = q;q = l;}//q->next == NULL 即q是最后一个结点q->next = p;L->next = q; //头结点指向原来的最后一个
}//单链表的升序排序（采用冒泡排序）
void sort_list(LinkList L)
{if(L==NULL||L->next->next==NULL)return;LNode *p,*q,*temp,*l,*tail;p = L;q = p->next;tail = NULL;while(L->next!=tail){p = L;q = p->next;while(q->next!=tail){l = q->next;if(l->data < q->data) //逆序{q->next=l->next;l->next=q;p->next=l;temp=l;l=q;q=temp;}p=q;q=l;}tail=q;//q->next==NULL,则q是最后一个}}//打印
void print(LinkList L)
{LinkList p = L;while(p!=NULL){p= p->next;printf("%dn",(p->data));}
}int main()
{LinkList L = NULL; //这里表示的已经是已经个指针了L = (LinkList )malloc(sizeof(LNode));if(L==NULL){return -1;}CreateList_L(L); //头插法建立单链表//CreateList_L2(L); //尾插法建立单链表//printf("%dn",Link_length(L)); //测试，输出链表长度//printf("%dn",GetElem(2,L)); //取得第二项元素对应的值//insert_head(L,4);//insert_tail(L,5);//int x;//delete_head(1,x,L);//测试删除是否成功//reserve(L);//倒置的测试//sort_list(L);//排序测试print(L);
}

//还要写单链表的排序

//逆置单链表

知识点

结构体的别名问题：

Node定义了一个Node型的节点对象，

PNode定义了一个指向Node型节点对象的Node型指针；

给这个指向node结构体指针类型的node定义了一个别名，

任何使用node*的地方都可以直接用PNode代替。

因使用时可能会忘记该别名是指针类型的，易犯错，不建议使用。

其他链表

循环链表

与单链表的区别仅在于，判别链表中最后一个结点的条件由“后继是否为空”变为“后继是否为头结点”

特点：

（1）对于单链表仅能从头结点开始遍历整个链表，而对于单循环链表则可以从表中任意结点开始遍历整个链表。

（2）有时对链表常做的操作是在表头、表尾进行，此时可以使用表尾标识链表，操作效率会提高。

双向链表

除了存在一个指向后继的指针域外，还存在一个指向前驱的指针域

操作特点

（1）“查询”和单链表相同

（2）“插入”和“删除”时需要同时修改两个方向上的指针；

插入：

newnode -> next = p -> next;
newnode -> prior = q->prior;
p -> next = newnode;
q -> prior = newnode;

删除：

p -> next = node -> next;
q -> prior = node -> prior;
free(node);

特点

(1) 从某个结点出发到其直接前驱结点或直接后继结点，时间复杂度均为O(1);

(2) 查找第i个结点、向第i个结点插入 或 删除第i个结点，都要区分是哪个方向；

(3) 如果是双向循环链表，修改指针要同时考虑在前驱结点和后继结点上的修改；

(4) 某个结点的直接前驱的直接后继，或它的直接后继的直接前驱，即为该结点本身。

静态链表
与借助数组来描述线性表的链式存储结构不同，静态链表结点也有数据域data和指针域next，

但是与前面所讲的链表中的指针有所不同的是，这里的指针是结点的相对地址（即数组的下标），称之为静态指针。
静态表适合于不支持指针的高级语言，或者最大元素值固定但插入、删除操作频繁的链表操作中，有关基于静态链表的操作与动态链表的相同。

特点：

（1）所有数据元素均存储在一个连续的空间段，但是相邻两个元素不一定处于相邻的空间。

（2）修改指针域即可以完成插入和删除操作，不需要移动数据元素，但是也不能随机访问静态链表的元素。

（3）一次性分配所有存储空间，插入、删除时无需再向操作系统申请或释放空间，但也限制了最大表长。