首页 / C语言 / C语言编程练习53:静态链表
C语言编程练习53:静态链表
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了C语言编程练习53:静态链表,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含5821字,纯文字阅读大概需要9分钟。
内容图文
![C语言编程练习53:静态链表](/upload/InfoBanner/zyjiaocheng/605/8a5c2b9f57894972ba17c77b5c4a1420.jpg)
题目描述
静态链表是使用顺序存储结构来实现的链表。严蔚敏《数据结构(C语言版)》在介绍静态链表时使用的是一个姓氏列表。 图1是书本上的静态链表示例,图(a)是初始化后插入了8个姓氏的链表,图(b)是在第5个元素前插入了“SHI”而删除了“WANG”的结果。![C语言编程练习53:静态链表 - 文章图片](/upload/getfiles/0001/2021/4/30/20210430092541868.jpg)
![C语言编程练习53:静态链表 - 文章图片](/upload/getfiles/0001/2021/4/30/20210430092541917.jpg)
![C语言编程练习53:静态链表 - 文章图片](/upload/getfiles/0001/2021/4/30/20210430092541982.jpg)
![C语言编程练习53:静态链表 - 文章图片](/upload/getfiles/0001/2021/4/30/20210430092542031.jpg)
![C语言编程练习53:静态链表 - 文章图片](/upload/getfiles/0001/2021/4/30/20210430092542092.jpg)
![C语言编程练习53:静态链表 - 文章图片](/upload/getfiles/0001/2021/4/30/20210430092542146.jpg)
输入
静态链表的存储空间(图2中的space)始终只有11个节点,起始为空表。insert a e代表在第a个姓氏前插入姓氏e;delete a代表删除第a个姓氏;search e代表查找姓氏e的位置;show代表输出静态链表存储空间的状态。输入保证操作都合法。输出
只遇到search和show时才输出。当遇到search时输出姓氏e在space中的位置;当遇到show时输出这11个结点的状态。姓氏占8个字符而数字占2个字符,姓氏左对齐。每个指令输出后面跟着含有20个星号的行。样例输入 Copy
show insert 1 ZHAO show insert 2 QIAN show insert 3 SUN show insert 4 LI insert 5 ZHOU insert 6 WU insert 7 ZHENG insert 8 WANG show insert 1 ZHANG show search LI show
样例输出 Copy
2 0 3 4 5 6 7 8 9 10 0 ******************** 3 2 ZHAO 0 4 5 6 7 8 9 10 0 ******************** 4 2 ZHAO 3 QIAN 0 5 6 7 8 9 10 0 ******************** 5 2 ZHAO 3 QIAN 4 SUN 0 6 7 8 9 10 0 ******************** 10 2 ZHAO 3 QIAN 4 SUN 5 LI 6 ZHOU 7 WU 8 ZHENG 9 WANG 0 0 ******************** 0 10 ZHAO 3 QIAN 4 SUN 5 LI 6 ZHOU 7 WU 8 ZHENG 9 WANG 0 ZHANG 2 ******************** 5 ******************** 0 10 ZHAO 3 QIAN 4 SUN 5 LI 6 ZHOU 7 WU 8 ZHENG 9 WANG 0 ZHANG 2 ********************
提示
提示:
1、怎样将字符串类型定义为ElemType呢?形如typedef int num一样,数组或者指针可以放在定义的类型名后面,例如将具有8个字符的姓氏定义为ElemType可以这样定义:typedef char ElemType[8]。
2、题目和书中给的算法描述还缺少静态链表的插入、删除以及显示,都需要自己写。
3、要求每个指令输出后跟一个空行,别忘了。
4、姓氏占8个字符,数字占2个字符,姓氏左对齐,可以这样输出printf("%-8s%2d");对于指令search也要输出占2个字符的数字。
5、静态链表初始化时将所有内存设为空,可以在InitSpace_SL中使用下面的方法:
memset(space, 0 ,sizeof(space));
总结:
静态链表与一般链表极为相似:使用数组来模拟内存,使用数组下表来模拟内存中的地址。
#include <iostream> #include <cstdio> #include <string> #include <queue> #include <stack> #include <algorithm> #include <cmath> #include <list> #include <cstdlib> #include <cstring> using namespace std; #define MAXSIZE 11//静态链表的长度 typedef char name[8];//元素的类型,规定姓氏不超过8个字符 typedef struct { name data;//节点中的数据 int cur;//下一个节点的下标 }NodeType;//节点类型 NodeType space[MAXSIZE]; typedef struct { int elem;//静态链表存储空间基址 int length;//静态链表中的元素数目 int listsize;//静态链表当前的长度 }SLinkList;//静态链表类型的定义 SLinkList s; void InitSpace_SL()//初始化 { //将一维数组space中的各分量连成一个备用链表,space【0】.cur为头指针 //‘0’表示空指针 memset(space,0,sizeof(space)); for(int i=0;i<MAXSIZE-1;++i) { space[i].cur=i+1; } space[0].cur=2; space[1].cur=0; space[MAXSIZE-1].cur=0; } int LocateElem_SL(SLinkList &s,name e) { //在静态链表中找到第一个值为e的元素 //若找到,返回他在链表中的位置,否则返回0 int i; i = s.elem;//i指示表中第一个节点 while(i&&strcmp(space[i].data,e)) { i = space[i].cur; } return i; } int Malloc_SL()//申请新的节点 { //若备用空间链表非空,则返回分配的结点下标,否则返回0 int i = space[0].cur; if(space[0].cur) { space[0].cur = space[space[0].cur].cur; } return i; } void Free_SL(int j) { //将下标为j的空闲节点回收到备用链表 space[j].cur = space[0].cur; space[0].cur = j; } void Insert(NodeType space[], int n, char b[])//插入 { int m = Malloc_SL(); strcpy(space[m].data, b); int j = 1, i = 1; while (j <n&&space[i].cur) { i = space[i].cur; j++; } space[m].cur = space[i].cur; space[i].cur = m; s.length++; } void Delete(int n) { int i,j=1; i =1; while (j<n&&space[i].cur) { j++; i= space[i].cur; } j = space[i].cur; space[i].cur = space[j].cur; space[j].cur = space[0].cur; space[0].cur = j; } void Search(char b[])//搜索 { int i = space[1].cur; while (i&&strcmp(space[i].data, b)) { i = space[i].cur; } printf("%2d\n", i); printf("********************\n"); } void Show()//输出 { for (int i = 0; i < 11; i++) { printf("%-8s%2d\n", space[i].data, space[i].cur); } printf("********************\n"); } int main() { char a[10], b[10]; int n; s.elem = 1, s.length = 0, s.listsize = 10; InitSpace_SL(); while (scanf("%s", a, 10) != EOF) { if (!strcmp("show", a)) { Show(); memset(a, 0, 10); } if (!strcmp("insert", a)) { scanf("%d", &n); scanf("%s", &b, 10); Insert(space, n, b); memset(a, 0, 10); memset(b, 0, 10); } if (!strcmp("delete", a)) { scanf("%d", &n); Delete(n); memset(a, 0, 10); } if (!strcmp("search", a)) { getchar(); scanf("%s", &b, 10); Search(b); memset(a, 0, 10); memset(b, 0, 10); } } return 0; }
代码来自:https://blog.csdn.net/qingchongxinshuru/article/details/51864528
内容总结
以上是互联网集市为您收集整理的C语言编程练习53:静态链表全部内容,希望文章能够帮你解决C语言编程练习53:静态链表所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。