《数据结构算法 编程实现样例详解》由会员分享,可在线阅读,更多相关《数据结构算法 编程实现样例详解(5页珍藏版)》请在金锄头文库上搜索。
1、数据结构算法编程实现样例详解请仔细阅读,建议打印。注意比较细节的差异,关于指针问题请看“难点答疑”编程 步骤程序结构框架样例源代码清单(以顺序表插入功能为例)一:编写 公共 头文 件引用的库文件定义系统常量建议文件名前加姓名:sjCommon.h#include #include #include #define OK 1#define ERROR 0#define TRUE 1#define FALSE 0二.*:编写 存储 结构 头文件定义元素类型定义结构体顺序:sjSeqList.h链式:sjLinList.h顺序表的结构体单链表的结构体#define ElemType int#defi
2、ne MAXSIZE 10typedef structElemType elemMAXSIZE;int last;SeqList;typedef char ElemType;typedef struct NodeElemType data;struct Node * next;Node, *LinkList;标准的线性表、栈、 队列、串的存储结构 样例顺序栈的结构体顺序队列的结构体#define Stack_Size 50 typedef struct StackElementTypeelemStack_Size;int top;SeqStack;#define MAXSIZE 50 type
3、def struct QueueElementTypeelementMAXSIZE;int front;int rear;SeqQueue;顺序串的结构体堆分配存储的串结构体#define MAXLEN 40 typedef struct char chMAXLEN; int len;SString;typedef structchar *ch;int len;HString;自定义结构体样例约瑟夫环结构体城市坐标结构体typedef struct dataint num; /用于存放人的序号int pwd; /用于存放密码 typedata;typedef struct nodetypeda
4、ta data;struct node *next;YSFNode, *YSFLinkList;typedef struct CityNodechar name10;float x;float y;struct CityNode *next;CityNode;三:编写 实现 所需 功能 的主 程序加载头文件#include sjCommon.h#include sjSeqList.h”应用教材现有的数据 结构算法1: 初始化顺序表int InitList(SeqList *L,int r) /*顺序表初始化,输入r个兀素 */ L-last =r-1;printf (请输入线性表的%d个儿素值
5、:n,r);for(int i=0; ilast; i+)scanf(%d,&L-elemi);return(OK);应用教材现有的数据 结构算法2:在顺序表L中第i个 数据兀素之前插入一 个儿素eint InsList(SeqList *L,int i,ElemType e)int k;if(i L-last+2) /*首先判断插入位置是否合法*/printf(插入位置i值不合法);return(ERROR);if(L-last= MAXSIZE-1)printf(表已满无法插入);return(ERROR);for(k=L-last;k=i-1;k-)/*为插入兀素而移动位置*/L-ele
6、mk+1=L-elemk;L-elemi-1=e;/*在C语言数组中,第i个元素的下标为i-1*/L-last+;return(OK);编写用户自定义算 法:输出顺序表中的所有儿素int DisplayList(SeqList *L)for(int i=0; ilast; i+)printf(%d - ,L-elemi);printf(%dn,L-elemi);return(OK);编程主函数main():定义需要的基本 类型和结构体类 型的变量调用前面的算void main()SeqList *l;int p,q;l=(SeqList*)malloc(sizeof(SeqList); /*
7、开辟顺序表存储空法,实现输入、间,返回起始位置*/处理、输出InitList(l,4);printf(顺序表中初始元素如下:n);DisplayList(l);printf(请输入要插入的位置:n);scanf(%d”,&p);printf(请输入要插入的元素值:n);scanf(%d”,&q);InsList(l,p,q);printf(插入后顺序表中元素如下:n);DisplayList(l);system(pause);难点答疑:关于C/C+语言中的结构体与指针1. 结构体和指针的引入原因我们已经知道数组,它用来保存线性数据,但是它有许多缺点:数组的大小是固定的,在程序运行期间是不能改变
8、的。我们在定义数组时必须足够大,保证程序 运行时不会溢出。但是,这也常常导致大量数组存储单元的浪费。数组需要一块连续的内存空间。但当应用程序较大,数组需要的内存块也较大时,这可能会降低 程序的效率。如果在数组元素中,有较多的插入操作,则被插元素后的元素需要向后移位,这也浪费机器的运 行时间。链表也是表示线性数据最有用的方法之一,用链表保存线性数据,可以克服数组的问题。使用链表数 据结构需要结构体和指针作为基础。2. 结构体的特点在实际问题中,一组数据往往具有不同的数据类型。例如,在学生登记表中,姓名应为字符型;学号 可为整型或字符型;年龄应为整型;性别应为字符型;成绩可为整型或实型。由于数组还
9、必须要求元素为 相同类型,显然不能用一个数组来存放这一组数据。因为数组中各元素的类型和长度都必须一致,以便于 编译系统处理。而结构数据类型(结构体)就可以解决这个问题。为了满足程序设计的需要,我们自己定义数据类型, 称之为自定义数据类型,结构是自定义数据类型中的一种,它可将多种数据类型组合在一起使用。3. 结构体的定义方法方法一:先定义结构体,再定义变量名方法一:在定义类型的同时定义变量struct Child (struct Child (double height;double height;char name10;char name10;int age;int age;char sex;
10、char sex;cha,chb;struct Child cha, chb;方法三:直接定义结构体变量struct double height;char name10;int age;char sex; cha, chb;这样,我们就定义了一个结构类型Child, struct是关键子。Child类型包含1个double、 1个int和2个char域(或成员),它可以与 C+的基本数据类型一样地使用。(注意)结 构类型定义也是一个语句,所以结尾必须有 分号(;),否则,会产生编译错误。同时定 义了两个Child类型的变量:cha, chb几点说明:(1) 结构体类型和结构型变量是不同的概念,
11、要先定义结构体类型,然后把变量定义为该结 构类型;只能对变量进行操作,编译时也只为变量分配存储空间;(2) 结构体中的成员可以单独使用(3) 成员也可以是一个结构体变量4. 结构体类型变量的引用结构体成员的引用方法:结构变量名.成员名如 cha.height=1.655. 结构体变量的初始化struct Child (double height;char name10;int age;char sex;cha=1.62,” 小诗”,20, F ;6. 结构体数组结构体类型的定义与前面的定义方法相同,只需把变量名定义成数组形式即可:如cha2结构体数组初始化举例:struct Child dou
12、ble height;char name10;int age;char sex;cha2=1.62, ”小诗”,20, F ,1.78, ”小飞”,22, M ;7. 为什么要用指针指针的好处在于:只要知道数据的位置就可以访问任何大小的数据。下图是一个简单的链表示意图:该链表由3个结点组成,其中每个结点都分为两个域,一个是数据域(即图中的大写字母A、B、C), 存放各种实际的数据,如学号num、姓名name、性别sex和成绩score等。另一个域为指针域,存放下一 结点的首地址。比如第一个结点的指针域存放的地址是1475,就是第二个结点的首地址。链表中的每一 个结点都是同一种结构类型。8. 指针使用说明(1)关于指针运算符两个运算*和&的作用正好相反,指针间接访问运算符*的意思是“指针指向的对象”,而地址运算符&的意思是“得到地址”,*从地址中获得数据的内容,而&获得该数据的地址。修改指针所指向的数据时要使用间接访问运算符*,要修改指针所指向的地址时,只需修改指针本身。例如:(*P)+将指针所指向的数据增加1,而P+则是将指针指向了下一个地址。(2)关于指针的进一步介绍9. 几种线性结构的算法实现总结(C语言实现)顺序表的建立与操作算法单链表的建立与操作算法栈的建立与基本操作的算法队列的建立与基本操作算法