数据结构1——linuxC（顺序表+单向链表）
一。顺序表
#include <stdio.h>
#define SEQ_SIZE 10
// 声明数据节点
struct seq_node{
int data;
};
// 遍历显示顺序表所有有效数据
void seq_show(struct seq_node *seq_list);
// 将该正数存放到顺序表中
void seq_add(int new_data, struct seq_node *seq_list);
// 将该数从顺序表中删除
void seq_del(int del_data, struct seq_node *seq_list);
// 当前数据总数
int g_sum=0;
int main()
{
// 1. 初始化顺序表（选用栈空间，结构体数组）
struct seq_node seq_list[SEQ_SIZE] = {0};
// 如果使用堆空间（实际使用与栈空间的数组是一模一样的！）
// struct seq_node *seq_list = calloc(SEQ_SIZE, sizeof(struct seq_node));
// 2.数据操作
int cmd;
while(1)
{
printf("Pls Input: ");
scanf("%d", &cmd); while(getchar()!='\n');
if(cmd>0)
seq_add(cmd, seq_list); // 将该正数存放到顺序表中
else if(cmd<0)
seq_del(-cmd, seq_list); // 将该数从顺序表中删除
seq_show(seq_list); // 遍历显示顺序表所有有效数据
}
return 0;
}
// 遍历显示顺序表所有有效数据
void seq_show(struct seq_node *seq_list)
{
int i;
for(i=0; i<g_sum; i++)
printf("%d ", seq_list[i].data);
printf("\n");
}
// 将该正数存放到顺序表中
void seq_add(int new_data, struct seq_node *seq_list)
{
// 0.判断当前数据总数是否已满。（限制最大长度）
if(g_sum >= SEQ_SIZE)
{
printf("SEQ_list FULL!!!!\n");
return;
}
// 1.将新数据放入指定位置
seq_list[g_sum].data = new_data;
// 2.当前数据总数++
g_sum++;
}
// 将该数从顺序表中删除
void seq_del(int del_data, struct seq_node *seq_list)
{
// 0.判断当前顺序表是否为空？提示并结束
if(g_sum == 0)
{
printf("SEQ_list Empty!!!!\n");
return;
}
// 1.循环逐个比对待删除数据del_data
int pos;
for(pos=0; pos<g_sum; pos++)
{
// 如果找到，提前跳出循环，记录下标pos
if(seq_list[pos].data == del_data)
break;
}
// 如果for循环正常结束，说明没找到。直接提示并结束
if(pos == g_sum)
{
printf("Not Found!\n");
return;
}
// 2.将后面的数据逐个向前覆盖。
int i;
// for(i=pos; i<=g_sum-2; i++)
for(i=pos; i<g_sum-1; i++)
{
// 如果不清楚他们的覆盖流程，可以添加printf打印语句，跟踪for循环。
// printf("2: %d = %d\n", seq_list[i].data, seq_list[i+1].data);
seq_list[i].data = seq_list[i+1].data;
}
// 3.当前数据总数g_sum--
g_sum--;
}二。单向链表
1.自定义3个链表数据节点
#include <stdio.h>
// 声明一个数据节点类型（取别名: node）
typedef struct node{
int data; // 数据域
struct node *next; // 指针域
}node;
int main()
{
/*
int var1=100;
int *p1 = &var1; // p1->var1
// 说法1：指针p1存储var1的地址
// 说法2：指针p1指向var1（更通用说法）
*/
// a.使用别名定义3个结构体变量，操作数据域
node a, b, c;
a.data = 100;
b.data = 200;
c.data = 300;
printf("%d %d %d\n",
a.data,
b.data,
c.data);
// b.操作他们的指针域，使他们形成a->b->c的指向关系
a.next = &b;
b.next = &c;
// c.通过a访问b的数据，再通过b访问c的数据
// printf("%.1f\n", (*p).score); // 不常用。先对指针进行解引用，再使用.访问成员
// printf("%.1f\n", p->score); // 更常用。只适用于结构体指针
// 更麻烦的写法：（不推荐）
printf("%d %d %d\n",
a.data,
(*(a.next)).data,
(*(b.next)).data);
// 更简单的写法：（更推荐）
printf("%d %d %d\n",
a.data,
a.next->data,
b.next->data);
// 如何通过a访问c的数据呢？
printf("c: %d\n", a.next->next->data);
return 0;
}2.3个链表数据节点指针(堆空间)
#include <stdio.h>
#include <stdlib.h>
// 声明一个数据节点类型（取别名: node）
typedef struct node{
int data; // 数据域
struct node *next; // 指针域
}node;
int main()
{
// 1.如果使用结构体指针*pa、*pb、*pc，分配堆空间后，应该如何实现相同效果？
node *pa = malloc(sizeof(node));
node *pb = malloc(sizeof(node));
node *pc = malloc(sizeof(node));
pa->data = 100;
pb->data = 200;
pc->data = 300;
printf("%d %d %d\n",
pa->data,
pb->data,
pc->data);
// 2.操作他们的指针域，形成链表
pa->next = pb;
pb->next = pc;
pc->next = NULL;
// 3.通过pa访问3个数据
printf("%d %d %d\n",
pa->data,
pa->next->data,
pa->next->next->data);
// 4.循环遍历访问（通过头节点pa访问所有节点）
node *pos;
for(pos=pa; pos!=NULL; pos=pos->next)
printf("%d ", pos->data);
printf("\n");
return 0;
}3.单向不循环链表.
#include <stdio.h>
#include <stdlib.h>
// 声明一个数据节点类型（取别名: node）
typedef struct node{
int data; // 数据域
struct node *next; // 指针域
}node;
// 初始化一个空节点
node *link_list_init(void);
// 添加数据到链表（头插法）
void link_list_add(int new_data, node *head);
// 添加数据到链表（尾插法）
void link_list_add_tail(int new_data, node *head);
// 链表遍历
void link_list_show(node *head);
// 节点删除（思路1：定义2个指针，记录前节点*pos_prev和欲删除节点*pos_del）
void link_list_del(int del_data, node *head);
// 节点删除（思路2：定义1个前节点指针*pos_prev，比较后节点的数据域）
void link_list_del2(int del_data, node *head);
int main()
{
// 1.初始化一条空链表（分配一个头节点堆空间）
node *head = link_list_init();
// 2.数据操作（正数新增，负数删除）
int cmd;
while(1)
{
printf("Pls Input: ");
scanf("%d", &cmd); while(getchar()!='\n');
if(cmd > 0)
// link_list_add(cmd, head); // 头插
link_list_add_tail(cmd, head); // 尾插
else if(cmd < 0)
link_list_del2(-cmd, head);
link_list_show(head);
}
return 0;
}
// 节点删除（思路1：定义2个指针，记录前节点*pos_prev和欲删除节点*pos_del）
void link_list_del(int del_data, node *head)
{
// 0.判断是否空链表（只有一个头节点）
if(head->next == NULL)
{
printf("ERROR: link list empty!\n");
return;
}
// 1.逐个对比，如不同，2个指针一起移动。如相同提前跳出
node *pos_prev = head;
node *pos_del;
for(pos_del=head->next; pos_del!=NULL; pos_del=pos_del->next)
{
if(pos_del->data == del_data)
break;
pos_prev = pos_del;
}
// 1.2 如循环正常结束，说明无此数据。
if(pos_del == NULL)
{
printf("ERROR: Not Found!\n");
return;
}
// 2.操作*pos_prev的指针域，指向*pos_del的指针域（后节点）
pos_prev->next = pos_del->next;
// 3.释放欲删除节点*pos_del的堆空间
free(pos_del);
}
// 节点删除（思路2：定义1个前节点指针*pos_prev，比较后节点的数据域）
void link_list_del2(int del_data, node *head)
{
// 0.判断是否空链表（只有一个头节点）
if(head->next == NULL)
{
printf("ERROR: link list empty!\n");
return;
}
// 1.遍历链表，逐个对比，如不同则向后移动，如相同则跳出，并记录欲删除节点地址*temp
node *pos_prev;
node *temp;
for(pos_prev=head; pos_prev->next!=NULL; pos_prev=pos_prev->next)
{
if(pos_prev->next->data == del_data)
{
temp = pos_prev->next;
break;
}
}
// 如果循环正常结束，说明无此数据
if(pos_prev->next == NULL)
{
printf("ERROR: Not Found!\n");
return;
}
// 2.将*pos_prev的指针域，指向欲删除节点的后节点
// pos_prev->next = pos_prev->next->next; // 效果与下行代码相同
pos_prev->next = temp->next;
// 3.释放欲删除节点的堆空间
free(temp);
}
// 链表遍历
void link_list_show(node *head)
{
node *pos;
for(pos=head->next; pos!=NULL; pos=pos->next)
printf("%d ", pos->data);
printf("\n");
}
// 添加数据到链表（尾插法）
void link_list_add_tail(int new_data, node *head)
{
// 1.找到尾节点（特点：指针域指向NULL）
node *pos_tail = head;
while(pos_tail->next != NULL)
pos_tail = pos_tail->next;
// 2.将新节点放到尾节点之后
link_list_add(new_data, pos_tail);
}
// 添加数据到链表（头插法）
void link_list_add(int new_data, node *head)
{
// 1.新节点申请堆空间，并将新数据放入
node *new = link_list_init();
new->data = new_data;
// 2.修改指针指向（注意前后顺序）
// a.先将头节点的指针域，给新节点的指针域（先偷）
new->next = head->next;
// b.让头节点的指针域，指向新节点
head->next = new;
}
// 初始化一个空节点
node *link_list_init(void)
{
// 1.申请堆空间
node *p = malloc(sizeof(node));
if(p == NULL) // 如果堆空间申请失败
{
printf("node malloc failed!");
return NULL;
}
// 2.清空节点
p->data = 0;
p->next = NULL;
// 3.成功则将堆空间返回
return p;
}4.用户信息管理
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 声明一个数据域结构体
typedef struct usr_info{
int id; // 用户ID
char name[20]; // 用户名
}datatype;
// 声明一个数据节点类型（取别名: node）
typedef struct node{
datatype data; // 数据域
struct node *next; // 指针域
}node;
// 显示用户信息
void usr_show(node *head);
// 新增用户信息
void usr_add(node *head);
// 删除用户信息
void usr_del(node *head);
// 初始化一个空节点
node *link_list_init(void);
// 链表遍历
void link_list_show(node *head);
// 添加数据到链表（头插法）
void link_list_add(datatype new_data, node *head);
// 添加数据到链表（尾插法）
void link_list_add_tail(datatype new_data, node *head);
// 节点删除（思路1：定义2个指针，记录前节点*pos_prev和欲删除节点*pos_del）
void link_list_del(datatype del_data, node *head);
#if 0
// 节点删除（思路2：定义1个前节点指针*pos_prev，比较后节点的数据域）
void link_list_del2(int del_data, node *head);
#endif
int main()
{
// 1.初始化一条空链表（分配一个头节点堆空间）
node *head = link_list_init();
// 为了调试简单，可预先添加一些测试数据
datatype test1 = {1, "Tom"};
datatype test2 = {10, "Jerry"};
link_list_add_tail(test1, head);
link_list_add_tail(test2, head);
// 2.用户信息操作
int cmd;
while(1)
{
printf("============1:CMD===============\n");
printf("0: 显示用户信息\n");
printf("1: 添加用户信息\n");
printf("2: 删除用户信息\n");
printf("3: 修改用户信息\n");
printf("4: 查询用户信息\n");
printf("Pls Input: ");
scanf("%d", &cmd); while(getchar()!='\n');
switch(cmd)
{
// 最好将<用户交互功能>，与<链表功能函数>分开。
case 0: usr_show(head); break;
case 1: usr_add(head); break;
case 2: usr_del(head); break;
// case 3: usr_update(head); break;
// case 4: usr_find(head); break;
}
}
return 0;
}
/******************** 用户交互功能函数 *********************/
// 显示用户信息
void usr_show(node *head)
{
printf("============2: Show===========\n");
printf("ID\t Name\n");
link_list_show(head);
printf("==============================\n");
}
// 新增用户信息
void usr_add(node *head)
{
// 1.提示用户输入信息
datatype input_data;
printf("============2: Add============\n");
printf("Pls Input New ID: ");
scanf("%d", &input_data.id); while(getchar()!='\n');
printf("Pls Input New Name: ");
scanf("%s", input_data.name); while(getchar()!='\n');
// 2.把数据添加到链表中。
link_list_add_tail(input_data, head);
}
// 删除用户信息
void usr_del(node *head)
{
// 1.提示用户输入信息
datatype input_data;
bzero(&input_data, sizeof(datatype));
int cmd;
printf("============2: Del============\n");
printf("1: 根据用户ID删除\n");
printf("2: 根据用户名删除\n");
printf("Pls Input: ");
scanf("%d", &cmd); while(getchar()!='\n');
// 2.输入详细信息
switch(cmd)
{
case 1:
printf("请输入删除的用户ID: ");
scanf("%d", &input_data.id); while(getchar()!='\n');
break;
case 2:
printf("请输入删除的用户名: ");
scanf("%s", input_data.name); while(getchar()!='\n');
break;
}
// 3.将指定数据节点删除。
link_list_del(input_data, head);
}
/******************** 链表操作功能函数 *********************/
// 链表遍历
void link_list_show(node *head)
{
node *pos;
for(pos=head->next; pos!=NULL; pos=pos->next)
printf("%d\t %s\n", pos->data.id, pos->data.name);
}
// 初始化一个空节点
node *link_list_init(void)
{
// 1.申请堆空间
node *p = malloc(sizeof(node));
if(p == NULL) // 如果堆空间申请失败
{
printf("node malloc failed!");
return NULL;
}
// 2.清空节点
bzero(&p->data, sizeof(datatype)); // 清空数据域
p->next = NULL;
// 3.成功则将堆空间返回
return p;
}
// 添加数据到链表（尾插法）
void link_list_add_tail(datatype new_data, node *head)
{
// 1.找到尾节点（特点：指针域指向NULL）
node *pos_tail = head;
while(pos_tail->next != NULL)
pos_tail = pos_tail->next;
// 2.将新节点放到尾节点之后
link_list_add(new_data, pos_tail);
}
// 添加数据到链表（头插法）
void link_list_add(datatype new_data, node *head)
{
// 1.新节点申请堆空间，并将新数据放入
node *new = link_list_init();
new->data = new_data;
// 2.修改指针指向（注意前后顺序）
// a.先将头节点的指针域，给新节点的指针域（先偷）
new->next = head->next;
// b.让头节点的指针域，指向新节点
head->next = new;
}
// 节点删除（思路1：定义2个指针，记录前节点*pos_prev和欲删除节点*pos_del）
void link_list_del(datatype del_data, node *head)
{
// 0.判断是否空链表（只有一个头节点）
if(head->next == NULL)
{
printf("ERROR: link list empty!\n");
return;
}
// 1.逐个对比，如不同，2个指针一起移动。如相同提前跳出
node *pos_prev = head;
node *pos_del;
for(pos_del=head->next; pos_del!=NULL; pos_del=pos_del->next)
{
if(pos_del->data.id == del_data.id)
break;
else if(strcmp(pos_del->data.name, del_data.name) == 0)
break;
pos_prev = pos_del;
}
// 1.2 如循环正常结束，说明无此数据。
if(pos_del == NULL)
{
printf("ERROR: Not Found!\n");
return;
}
// 2.操作*pos_prev的指针域，指向*pos_del的指针域（后节点）
pos_prev->next = pos_del->next;
// 3.释放欲删除节点*pos_del的堆空间
free(pos_del);
}
#if 0
// 节点删除（思路2：定义1个前节点指针*pos_prev，比较后节点的数据域）
void link_list_del2(int del_data, node *head)
{
// 0.判断是否空链表（只有一个头节点）
if(head->next == NULL)
{
printf("ERROR: link list empty!\n");
return;
}
// 1.遍历链表，逐个对比，如不同则向后移动，如相同则跳出，并记录欲删除节点地址*temp
node *pos_prev;
node *temp;
for(pos_prev=head; pos_prev->next!=NULL; pos_prev=pos_prev->next)
{
if(pos_prev->next->data == del_data)
{
temp = pos_prev->next;
break;
}
}
// 如果循环正常结束，说明无此数据
if(pos_prev->next == NULL)
{
printf("ERROR: Not Found!\n");
return;
}
// 2.将*pos_prev的指针域，指向欲删除节点的后节点
// pos_prev->next = pos_prev->next->next; // 效果与下行代码相同
pos_prev->next = temp->next;
// 3.释放欲删除节点的堆空间
free(temp);
}
#endif5.单向循环链表
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
// 声明一个数据节点类型（取别名: node）
typedef struct node{
int data; // 数据域
struct node *next; // 指针域
}node;
// 初始化一个空节点
node *link_list_init(void);
// 添加数据到链表（头插法）
void link_list_add(int new_data, node *head);
// 添加数据到链表（尾插法）
void link_list_add_tail(int new_data, node *head);
// 链表遍历
void link_list_show(node *head);
// 节点删除（思路1：定义2个指针，记录前节点*pos_prev和欲删除节点*pos_del）
void link_list_del(int del_data, node *head);
// 节点删除（思路2：定义1个前节点指针*pos_prev，比较后节点的数据域）
void link_list_del2(int del_data, node *head);
// 添加数据到链表（有序插入）
void link_list_add_order(int new_data, node *head);
// 链表数据逆转
void link_list_reverse(node *head);
int main()
{
// 1.初始化一条空链表（分配一个头节点堆空间）
node *head = link_list_init();
// 2.数据操作（正数新增，负数删除）
int cmd;
while(1)
{
printf("Pls Input: ");
scanf("%d", &cmd); while(getchar()!='\n');
if(cmd > 0)
link_list_add_tail(cmd, head); // 尾插
else if(cmd < 0)
link_list_del(-cmd, head); // 删除
else if(cmd == 0)
{
// 一直循环打印每个数据
node *pos = head->next;
while(1)
{
printf("%d\n", pos->data);
pos=pos->next;
if(pos == head)
pos=pos->next;
sleep(1); // 延时1秒
}
}
link_list_show(head);
}
return 0;
}
#if 0
// 节点删除（思路2：定义1个前节点指针*pos_prev，比较后节点的数据域）
void link_list_del2(int del_data, node *head)
{
// 0.判断是否空链表（只有一个头节点）
if(head->next == NULL)
{
printf("ERROR: link list empty!\n");
return;
}
// 1.遍历链表，逐个对比，如不同则向后移动，如相同则跳出，并记录欲删除节点地址*temp
node *pos_prev;
node *temp;
for(pos_prev=head; pos_prev->next!=NULL; pos_prev=pos_prev->next)
{
if(pos_prev->next->data == del_data)
{
temp = pos_prev->next;
break;
}
}
// 如果循环正常结束，说明无此数据
if(pos_prev->next == NULL)
{
printf("ERROR: Not Found!\n");
return;
}
// 2.将*pos_prev的指针域，指向欲删除节点的后节点
// pos_prev->next = pos_prev->next->next; // 效果与下行代码相同
pos_prev->next = temp->next;
// 3.释放欲删除节点的堆空间
free(temp);
}
// 链表数据逆转
void link_list_reverse(node *head)
{
// 1.判断是否为空链表（只有一个头节点）
if(head->next == NULL)
{
printf("ERROR: link list empty!\n");
return;
}
// 2.遍历链表，找到尾节点 pos_tail
node *pos_tail = head;
while(pos_tail->next != NULL)
pos_tail = pos_tail->next;
// 3.循环将第一个数据节点，以头插形式插入到 pos_tail 之后，直到第一个数据节点为pos_tail
node *pos;
int temp_data;
for(pos=head->next; pos!=pos_tail; pos=head->next)
{
// 移动
// 下列写法是错误的，已经被free释放的堆空间不允许被再次访问！
// link_list_del(pos->data, head);
// link_list_add(pos->data, pos_tail);
// 暂存数据域
temp_data = pos->data;
link_list_del(temp_data, head);
link_list_add(temp_data, pos_tail);
}
}
// 添加数据到链表（有序插入）
void link_list_add_order(int new_data, node *head)
{
// 1.遍历链表，找出比新数据大的节点pos，并记录前节点pos_prev
node *pos;
node *pos_prev=head;
for(pos=head->next; pos!=NULL; pos=pos->next)
{
if(pos->data > new_data)
break;
// pos_prev = pos_prev->next; // 效果与下行一模一样
pos_prev = pos;
}
// 2.使用头插法函数，插入到pos_prev之后
link_list_add(new_data, pos_prev);
}
#endif
// 节点删除（思路1：定义2个指针，记录前节点*pos_prev和欲删除节点*pos_del）
void link_list_del(int del_data, node *head)
{
// 0.判断是否空链表（只有一个头节点）
if(head->next == head)
{
printf("ERROR: link list empty!\n");
return;
}
// 1.逐个对比，如不同，2个指针一起移动。如相同提前跳出
node *pos_prev = head;
node *pos_del;
for(pos_del=head->next; pos_del!=head; pos_del=pos_del->next)
{
if(pos_del->data == del_data)
break;
pos_prev = pos_del;
}
// 1.2 如循环正常结束，说明无此数据。
if(pos_del == head)
{
printf("ERROR: Not Found!\n");
return;
}
// 2.操作*pos_prev的指针域，指向*pos_del的指针域（后节点）
pos_prev->next = pos_del->next;
// 3.释放欲删除节点*pos_del的堆空间
free(pos_del);
}
// 添加数据到链表（尾插法）
void link_list_add_tail(int new_data, node *head)
{
// 1.找到尾节点（特点：指针域指向头节点head）
node *pos_tail = head;
while(pos_tail->next != head)
pos_tail = pos_tail->next;
// 2.将新节点放到尾节点之后
link_list_add(new_data, pos_tail);
}
// 添加数据到链表（头插法）
void link_list_add(int new_data, node *head)
{
// 1.新节点申请堆空间，并将新数据放入
node *new = link_list_init();
new->data = new_data;
// 2.修改指针指向（注意前后顺序）
// a.先将头节点的指针域，给新节点的指针域（先偷）
new->next = head->next;
// b.让头节点的指针域，指向新节点
head->next = new;
}
// 链表遍历
void link_list_show(node *head)
{
node *pos;
for(pos=head->next; pos!=head; pos=pos->next)
printf("%d ", pos->data);
printf("\n");
}
// 初始化一个空节点
node *link_list_init(void)
{
// 1.申请堆空间
node *p = malloc(sizeof(node));
if(p == NULL) // 如果堆空间申请失败
{
printf("node malloc failed!");
return NULL;
}
// 2.清空节点
p->data = 0;
p->next = p;
// 3.成功则将堆空间返回
return p;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-02-17，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
