[数据结构] 链表
写在前面
菜鸡博主开始复习了，先从数据结构开始吧（其实是每天复习高数太累了）
1. 单链表
单链表是线性表的链式存储，是指通过一组任意的存储单元来存储线性表中的数据元素。对每个链表节点，除了存放元素自身的信息之外，还需要存放一个指向其后继的指针（如下图所示）
单链表的节点可以用如下代码描述：
typedef struct Node {
int data;
struct Node *next;
}Node, *LinkedList;
// Node表示节点的类型，LinkedList表示指向Node节点类型的指针类型
1）单链表的初始化
初始化主要完成以下工作：创建一个单链表的前驱节点并向后逐渐逐步添加节点，用代码可以表示为：
LinkedList InitList() {
Node *L;
L = (Node *)malloc(sizeof(Node)); // 创建头节点，开辟内存
if(L == NULL)
printf("申请内存失败");
L->next = NULL;
}
[注]：判断内存是否开辟失败是很有必要的，虽然可以省略不写！
2）头插法创建单链表
利用指针向下一个节点元素的方式进行逐个创建，得到的结果是逆序的，如图所示：
从一个空表开始，生成新结点，并将读取到的数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头，即头结点之后。
LinkedList HeadCreatedList() {
Node *L;
L = (Node *)malloc(sizeof(Node));
L->next = NULL;
int x; // x为链表数据域中的数据
while(scanf("%d", &x) != EOF) {
Node *p;
p = (Node *)malloc(sizeof(Node)); // 申请新节点
p->data = x; // 节点数据域赋值
p->next = L->next; // 将节点插入到表头 L --> |2| --> |1| --> NULL
L->next = p;
}
return L;
}
3）尾插法创建单链表
头插法生成的链表中，结点的次序和输入数据的顺序不一致。若希望两者次序一致，则需要尾插法。
必须增加一个尾指针r，使其始终指向当前链表的尾节点
LinkedList TailCreatedList() {
Node *L;
L = (Node *)malloc(sizeof(Node));
L->next = NULL;
Node *r;
r = L; // r开始时指向头节点
int x;
while(scanf("%d", &x) != EOF) {
Node *p;
p = (Node *)malloc(sizeof(Node));
p->data = x;
r->next = p;
r = p;
}
r->next = NULL;
return L;
}
4）遍历单链表
遍历输出的思路：建立一个指向链表L的节点，沿着链表L向后搜索
void PrintList(LinkedList L) {
Node *p = L->next;
int i = 0;
while(p) {
printf("第%d个元素的值为%d", ++ i, p->data);
p = p->next;
}
}
我们也可以把其中的某个值x改成k
LinkedList ReplaceList(LinkedList L, int x, int k) {
Node *p = L->next;
int i = 0;
while(p) {
if(p->data == x)
p->data = k;
p = p->next;
}
return L;
}
5）插入、删除
链表的插入操作主要分为查找到第i个位置，将该位置的next指针修改为指向我们新插入的节点，而新插入的节点next指针指向我们i+1个位置的节点。
其操作方式可以设置一个前驱节点，利用循环找到第i个位置，再进行插入。
如图，在DATA1和DATA2数据节点之中插入一个NEW_DATA数据节点：
LinkedList ListInsert(LinkedList L, int i, int x) {
Node *pre = L; // 指针p指向当前扫描到的节点
int j = 0;
while(pre != NULL && j < i - 1) { // 循环找到第i-1个节点
pre = pre->next;
j ++;
}
if(p == NULL)
return 0;
Node *s = (Node *)malloc(sizeof(Node));
s->data = x;
s->next = pre->next;
pre->next = s;
return L;
}
删除元素要建立一个前驱结点和一个当前结点，当找到了我们需要删除的数据时，直接使用前驱结点跳过要删除的结点指向要删除结点的后一个结点，再将原有的结点通过free函数释放掉。如图所示：
LinkedList ListDelete(LinkedList L, int x) {
Node *p, *pre; // pre为前驱，p为查找的节点
p = L->next;
while(p->data != x) {
pre = p;
p = p->next;
}
pre->next = p->next;
free(p);
return L;
}
6）合并递增单链表
struct ListNode* mergeLists(struct ListNode* l1, struct ListNode* l2) {
struct ListNode dummy; // 创建虚拟头节点
struct ListNode* tail = &dummy; // 创建尾节点指针
while (l1 != NULL && l2 != NULL) { // 遍历两个链表
if (l1->val < l2->val) { // 如果l1的值小于l2的值
tail->next = l1; // 将l1添加到新链表中
l1 = l1->next; // 移动l1指针到下一个节点
} else { // 如果l2的值小于等于l1的值
tail->next = l2; // 将l2添加到新链表中
l2 = l2->next; // 移动l2指针到下一个节点
}
tail = tail->next; // 移动尾节点指针到新链表的尾部
}
if (l1 != NULL) { // 如果l1还有剩余节点
tail->next = l1; // 将剩余节点添加到新链表的尾部
} else { // 如果l2还有剩余节点
tail->next = l2; // 将剩余节点添加到新链表的尾部
}
return dummy.next; // 返回新链表的头节点
}
7）逆序
直接给出完整可运行代码叭
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
struct ListNode {
int val;
struct ListNode *next;
};
// 创建一个包含n个随机整数的单链表
struct ListNode * createList(int n) {
struct ListNode *head = NULL, *tail = NULL;
for(int i = 0; i < n; i ++) {
struct ListNode *node = (struct ListNode *)malloc(sizeof(struct(ListNode)));
node->val = rand() % 100; // 随机生成一个0-99的整数作为节点的值
node->next = NULL;
if(tail == NULL)
head = tail = node; // 链表为空，则将头指针和尾指针指向新节点
else {
tail->next = node;
tail = node;
}
}
return head;
}
// 打印链表
void printList(struct ListNode *head) {
while(head != NULL) {
printf("%d ", head->val);
head = head->next;
}
printf("\n");
}
// 逆序
void reverseList(struct ListNode **head) {
if(*head == NULL || (*head)->next == NULL) {
//若链表为空或只有一个节点
return ;
}
struct ListNode *prev = NULL, *curr = *head, *next = NULL;
while(curr != NULL) { // 遍历链表，将每个节点的后继指针指向前一个节点
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
*head = prev; // 将头指针指向逆序后的链表头节点
}
int main() {
srand(time(NULL));
struct ListNode *L = createList(5);
printf("The original list is: ");
printList(L);
reverseList(&L);
printf("The new list is: ");
printList(L);
return 0;
}
2.双链表
其中，DATA表示数据，其可以是简单的类型也可以是复杂的结构体；
pre代表的是前驱指针，它总是指向当前结点的前一个结点，如果当前结点是头结点，则pre指针为空；
next代表的是后继指针，它总是指向当前结点的下一个结点，如果当前结点是尾结点，则next指针为空
结构体定义为：
typedef struct line {
int data;
struct line *pre;
struct line *next;
}line, *a;
1）创建
line *InitLine(line *head) {
// 节点数量，当前位置，输入的数据
int number, pos = 1, inputdata;
printf("请输入创建节点的大小");
scanf("%d", &number);
printf("\n");
if(number < 1)
return NULL;
head = (line *)malloc(sizeof(line));
head->pre = NULL;
head->next = NULL;
printf("输入第%d个数据\n"，pos ++);
scanf("%d", inputdata);
head->data = inputdata;
line *list = head;
while(pos <= number) {
line *body = (line *)malloc(sizeof(line));
body->pre = NULL;
body->next = NULL;
printf("输入第%d个数据\n", pos ++);
scanf("%d", &inputdata);
body->data = inputdata;
list->next = body;
body->pre = list;
list = list->next;
}
return head;
}
2）插入
line *InsertLine(line *head, int data, int location) {
line *temp = (line *)malloc(sizeof(line));
temp->data = data;
temp->pre = NULL;
temp->next = NULL;
if(location == 1) {
temp->next = head;
head->pre = temp;
head = temp;
} else {
line *body = head;
for(int i = 1; i < location )
body = body->next;
// 若插入位置在链表尾
if(body->next == NULL) {
body->next = temp;
temp->pre = body;
} else {
body->next->pre = temp;
temp->next = body->next;
body->next = temp;
temp->pre = body;
}
}
return head;
}
3）删除
line *DeletaLine(line *head, int data) {
line *list = head;
while(list) {
if(list->data == data) {
list->pre->next = list->next;
list->next->pre = list->pre;
free(list);
return head;
}
list = list->next;
}
printf("未找到该元素，删除失败");
return head;
}
再给出一个题目的代码
实现程序利用顺序表完成一个班级的一个学期的所有课程的管理：能够增加、删除、修改学生的成绩记录。
是博主在大二的时候写的，可能风格不太统一（还是太懒了）
#include<stdio.h>
#include<stdlib.h> //使用malloc得加入这个头文件
#include<string.h> //使用strcmp
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
#define MAXLEN 100
typedef struct node
{
int num; //学号
char name[MAXLEN]; //姓名
float score; //成绩
struct node *next;
}linklist,*LinkList;
void creat(linklist *&L) //创建链表空白头节点
{
L = (linklist *)malloc(sizeof(linklist));
L->num=0;
L->name[0]='\0';
L->score=0;
L->next=NULL;
}
void AddStu(linklist *&L) //添加学生
{
int x;
linklist *s = NULL, *r = L; //s指向创建的结点 r是尾指针
printf("请输入学生学号(输入0以结束):");
scanf("%d",&x);
while(x!=0)
{
s=(linklist *)malloc(sizeof(linklist));
s->num=x;
printf("请输入姓名:"); scanf("%s",s->name);
printf("请输入成绩:"); scanf("%f",&s->score);
r->next=s;
r=s;
printf("\n");
printf("请输入学生学号(输入0以结束):");
scanf("%d",&x);
}
r->next = NULL;
}
int listLength(LinkList L) //不要头结点求表长
{
int n = 0;
LinkList p = L; //定义遍历指针
p = p->next;
while (p != NULL)
{
n++;
p=p->next;
}
return n; //得到的长度
}
void SearchStu(LinkList L) //查找学生
{
int c;
if(L->next==NULL) printf("无学生信息\n");
else
{
LinkList p;
p=L->next;
int id;
char name1[MAXLEN];
printf("按学号查找请输入1\t按姓名查找请输入2\t\n");
scanf("%d",&c);
if(c==1)
{
printf("请输入学生学号:");
scanf("%d",&id);
while((p->num!=id)&&(p!=NULL))
{
p=p->next;
}
if(p!=NULL) printf("学号:%d 姓名:%-15s 成绩:%5.1f\n",p->num,p->name,p->score);
else printf("未查到该学生\n");
}
else
{
printf("请输入学生姓名:");
scanf("%s",name1);
while((strcmp(name1,p->name)!=0)&&(p!=NULL))
{
p=p->next;
}
if(p!=NULL) printf("学号:%d 姓名:%-15s 成绩:%5.1f\n",p->num,p->name,p->score);
else printf("未查到该学生\n");
}
}
}
void StuInsert(LinkList L) //插入学生
{
LinkList p,t;
p=L;
int index;
int l;
int i;
printf("请输入插入的位置：");
scanf("%d",&index);
l=listLength(L);
if(index>l+1)
{
printf("插入位置超出表长且非表末端！\n");
}
else
{
for(i=0;i<index-1;i++) //找前驱结点
p=p->next;
t=(linklist *)malloc(sizeof(linklist));
printf("请输入学号:"); scanf("%d",&t->num);
printf("请输入姓名:"); scanf("%s",t->name);
printf("请输入成绩:"); scanf("%f",&t->score);
t->next=p->next;
p->next=t;
}
}
Status listDelete(linklist *&L) //删除（学号）
{
int del;
printf("请输入要删除的学生的学号：");
scanf("%d",&del);
linklist *p1,*p2; //p1指向前驱结点，p2指向删除结点
p1=L;
p2=L->next;
while(p2!=NULL && p2->num!=del)
{
p1=p2;
p2=p2->next;
}
if(p2==NULL) printf("未找到该生，删除失败！");
else
{
p1->next=p2->next;
free(p2);
}
return OK;
}
void printList(linklist *L) //输出链表
{
LinkList p = L;
p = p->next; //因为头结点没有数据，所以移动到下一个结点
printf("单链表显示：\n");
if(p == NULL) printf("空表\n");
while (p != NULL)
{
printf("学号:%d 姓名:%-15s 成绩:%5.1f\n",p->num,p->name,p->score);
p = p->next;
}
}
void Menu() //文本菜单
{
printf(" *****************************\n");
printf(" * 学生成绩管理系统菜单 *\n");
printf(" *****************************\n");
printf(" + 1.查看学生 +\n");
printf(" + 2.添加学生 +\n");
printf(" + 3.插入学生 +\n");
printf(" + 4.查找学生 +\n");
printf(" + 5.删除学生 +\n");
printf(" + 6.显示菜单 +\n");
printf(" + 0.退出 +\n");
printf(" *****************************\n");
}
int main()
{
int choose;
LinkList L=NULL;
creat(L);
Menu();
printf("请输入要执行功能的序号:");
scanf("%d",&choose);
while(choose!=0)
{
switch(choose)
{
case 1:printList(L);printf("\n");break;
case 2:AddStu(L);printf("\n");break;
case 3:StuInsert(L);printf("\n");break;
case 4:SearchStu(L);printf("\n");break;
case 5:listDelete(L);printf("\n");break;
case 6:Menu();printf("\n");break;
default: printf("输入错误！请重新输入！\n");break;
}
printf("请输入要执行功能的序号:");
scanf("%d",&choose);
}
if(choose==0) printf("感谢使用！\n");
return 0;
}
写在最后
在顺序表中做插入删除操作时，平均移动大约表中一半的元素，因此对n较大的顺序表效率低。 并且需要预先分配足够大的存储空间，估计过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。而链表恰恰是其中运用的精华。
博主实在是太懒了，循环链表也不高兴写了，下次想起来并且愿意的话再补吧（bushi