动态链表
链表的定义
前置知识
- 主要涉及结构体，指针，以及函数的知识
链表的储存
-
本文章主要采用的是链式储存的方法
-
需要定义一个结构体，包括数据以及之战两部分
struct node { int data; //储存当前结点的数值 struct node * next; //存放下一个结点的地址 }; -
为了方便之后操作我们可以用
typedef对结构体类型重命名typedef struct node { int data; struct node * next; } Node; -
接下来我们试在主函数中，创建空链表
Node * head = NULL; //指针指向空 -
最后要释放连接
void freeList(Node ** pHead) { Node * p = *pHead; Node * pre; while (p != NULL) { pre = p; p = p->next; free(pre); } *pHead = NULL; }
按顺序插入数据（尾插）
- 大致思路为将前一个结点的指针指向新结点
- 新结点的指针应当指向空结点（成为尾节点）
- 注意：当原有链表为空时，要将主函数中的头结点指向新结点
//因为要对头结点进行修改，所以传入的时头节点的地址
//头结点地址，加入的数据
void push_back_list(Node ** phead, int data)
{
//动态链表要申请动态的内存
Node * newNode = (Node *)malloc(sizeof(Node));
newNode->data = data;
newNode->next = NULL;
// 判断原链表是否为空链表
if (*phead == NULL)
{
*phead = newNode;
}
else
{
Node * temp = *pHead;
// 循环判断寻找尾结点
while (temp->next != NULL)
temp = temp->next; // 原链表尾节点指向新节点
temp->next = newNode;
}
}
常见链表操作
链表元素统计与打印
- 主要依靠循环遍历
void printList(Node * head)
{
Node * p;
for (p=head; p!=NULL; p=p->next)
printf("%d ", p->data); //等价于 `*p.`
puts("");
}
int size_list(Node *phead)
{
int cnt = 0;
Node *p;
for(p = phead; p != NULL; p = p->next)
cnt ++;
return cnt;
}
插入结点
- 含n个结点的链表有n+1个位置可以插入，插到n位置需要n + 1次（找到插入位置之前的结点）
- 先将新结点的指针指向后结点再将前结点的指针指向新结点
- 顺序反过来会产生环，而且会丢失数据
- 顺序反过来会产生环，而且会丢失数据
//头结点地址，插入位置，插入数据
void insert_list(Node **phead,int index, int date)
{
if(index < 0 || index > size_list(*phead))
return;
Node *newNode;
newNode = (Node*)malloc(sizeof(Node));
newNode -> next = NULL;
newNode -> data = date;
//特判插入头结点时
if(index == 0)
{
newNode->next = *phead;
*phead = newNode;
return;
}
Node *p;
p = *phead;
int i;
for(i = 0; i < index - 1; i ++)
p = p ->next;
newNode->next = p->next;
p->next = newNode;
}
删除结点(删除所有出现的某个数)
-
将需要删除结点
a的前一个结点的指针指向a后的一个结点 -
删除头结点时需特殊处理（不需要再找它前面的结点）
-
删除第一次出现的某个数思想类似，将循环稍加改动即可
//头结点地址以及需要删除的数字
//随删随释放内存
void delete_list(Node **phead, int date)
{
Node *p = *phead;
while(p->next != NULL)
{
if(p->next->data == date)
{
Node *t = p->next;
p ->next = t->next;
free(t);
}
else p = p->next;
}
p = *phead;
if(p->data == date)
{
*phead = p->next;
free(p);
}
}
t = t->next;
free(t);
}
else p = p->next;
}
p = *phead;
if(p->data == date)
{
*phead = p->next;
free(p);
}
}
练习
实现一个具有如下功能的电话本
-------------------------
超级电子号码本
------------------------
1 ：添加号码
2 ：查询号码
3 ：删除号码
4 ：打印所有号码
5 ：退出
------------------------
请选择您好进行的操作：
// 1: 依次输入姓名和号码
// 2、3: 根据姓名查号码
// 4: 按照添加顺序打印
code
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <windows.h>
typedef struct number
{
char name[100];
char phone_num[100];
} Number;
typedef struct node
{
Number data;
struct node * next;
} Node;
void print_menu()
{
puts("------------------------");
puts(" 1 ：添加号码 ");
puts(" 2 ：查询号码");
puts(" 3 ：删除号码");
puts(" 4 ：打印所有号码");
puts(" 5 ：退出");
puts(" ------------------------");
printf("请选择您好进行的操作：");
}
void print_list(Node *head)
{
Node *p;
for(p = head; p != NULL; p = p->next)
printf("%s\t%s\n", p->data.name, p->data.phone_num);
}
Node *push_back(Node *head)
{
Node *p;
Node * new_node = (Node *)malloc(sizeof(Node));
new_node->next = NULL;
puts("请输入需要储存的姓名：");
scanf("%s", new_node->data.name);
puts("请输入需要储存的号码：");
scanf("%s", new_node->data.phone_num);
if(head == NULL)
{
return new_node;
}
p = head;
while(p->next != NULL)
p = p ->next;
p->next = new_node;
return head;
}
void find_list(Node *head)
{
Node *p = head;
char name[100];
if(head == NULL)
{
puts("当前电话本为空, 无法进行删除！");
return ;
}
puts("请输入要查询的姓名：");
scanf("%s", name);
for(p = head; p != NULL; p = p->next)
{
if(strcmp(p->data.name, name) == 0)
printf("%s\t%s\n", p->data.name, p->data.phone_num);
return;
}
puts("未找到此纪录！");
}
Node *delete_list(Node *head)
{
char name[100];
Node *p = head;
if(head == NULL)
{
puts("当前电话本为空, 无法进行删除！");
return head;
}
puts("请输入你需要删除信息的姓名：");
scanf("%s", name);
while(p ->next != NULL)
{
if(strcmp(p->next->data.name, name) == 0)
{
Node *t = p->next;
p->next = t->next;
free(t);
}
else p = p->next;
}
p = head;
if(strcmp(p->data.name, name) == 0)
{
head = p->next;
free(p);
}
puts("删除成功！");
return head;
}
int main()
{
Node *head = NULL;
int op;
while(1)
{
system("cls");
print_menu();
scanf("%d", &op);
switch(op)
{
case 1:
head = push_back(head);
break;
case 2:
find_list(head);
system("pause");
break;
case 3:
head = delete_list(head);
system("pause");
break;
case 4:
print_list(head);
system("pause");
break;
case 5:
puts("欢迎下次使用！");
return 0;
default :
break;
}
}
return 0;
}
