丫丫的宝贝
范文一：单链表的实验
单链表实验
一、实验目的
1、掌握用Visual C++6.0上机调试单链表的基本方法
2、掌握单链表的插入、删除、查找、求表长以及有序单链表的合并算法的实现
二、实现内容
1、单链表基本操作的实现
[问题描述]要在带头结点的单链表h 中第i 个数据元素之前插入一个数据元素x ，首先需要在单链表中寻找到第i-1个结点并用指针p 指示，然后申请一个由指针s 指示的结点空间，并置x 为其数据域值，最后修改第i-1个结点，并使x 结点的指针指向第i 个结点，要在带头结点的单链表h 中删除第i 个结点，首先要计数寻找到第i 个结点并使指针p 指向其前驱第i-1个结点，然后删除第i 个结点并释放被删除结点空间。
[基本要求]用链式存储结构实现存储
[实现提示]链式存储结构不是随机存储结构，即不能直接取到单链表中某个结点，而要从单链表的头结点开始一个一个地计数寻找。
2、求表长以及有序单链表的合并算法的实现
[问题描述] 假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递增次序排列的单链表，并计算表长。要求利用原来两个单链表的结点存放归并后的单链表。
[基本要求]用链式存储结构实现存储
源代码：
#include #include #include #define maxsize 100 #define null 0 typedef int ElemType; using namespace std; typedef struct List { int data; struct List *next; }List; List InitList(List *head) //构造链表 { int i,n; List *p,*q; if (!head) exit(0); q = head; head->data = 0; head->next = null; cout<<" 数组的总个数为："=""> cin>>n; for (i=1;i<> { p = (List*)malloc(sizeof (List)); if (!p) exit(0); cout<<" 输入第"=""><><<" 个数据："=""> cin>>p->data; p->next =q->next; q->next = p; q = p; } } void showList(List *head) { List *p; p = head->next; while (p!=null) { cout p = p->next; } cout<> } void insert(List *head,int position,int e) { List *p,*q; p = head; q = (List*)malloc(sizeof (List)); int j = 0; while ((p!=null)&&(j<> { p = p->next; j = j + 1; } if ((p==null)||(j>position-1)) { cout<<" 插入位置错误！"=""><> } else { q->data = e; q->next = p->next; p->next = q; } } void length(List *head) { int m =0; List *p; p = head; while (p->next!=null) { p = p->next; m = m+1; } cout<><> } void Delete(List *head,int pos) { List *p,*q; p = head; int j; j = 0; q = (List*)malloc(sizeof (List)); while (p->next&&j<> { p = p->next; j = j+1; } if (!(p->next)||j>pos-1) cout<<" 删除位置不合理！"=""><> else { q = p->next; p->next = q->next; delete (q); } } void mergeList(List *head1,List *head2) { List *p,*q; List *h,*r,*m; h = (List*)malloc(sizeof (List)); r = h; m = h; p = head1->next;q = head2->next; while (p&&q) { if (p->data<=q->data) { r->next = p; r = r->next; p = p->next; } else { r->next = q; r = r->next; q = q->next; } } if (p==null) { while (q != null) { r->next = q; r = r->next; q = q->next; } } else if (q == null) { while (p != null) { r->next =p; r = r->next; p = p->next; } } m = h->next; while (m != null) { cout<<"> m = m->next; } } int main() { int position,e,pos; int ch; List *head; head = (List*)malloc(sizeof (List)); List InitList(List *head) ; void showList(List *head); void insert(List *head,int position,int e); void length(List *head); void Delete(List *head,int pos); List *head1,*head2; head1 = (List*)malloc(sizeof (List)); head2 = (List*)malloc(sizeof (List)); while (1) { cout<<"> *******************"<> cout<<" *="" 1.创建链式表=""><> cout<<" *="" 2.表现链式表=""><> cout<<" *="" 3.删除线性表=""><> cout<<" *="" 4.线性表插值=""><> cout<<" *="" 5.链表长度=""><> cout<<" *="" 6.两个链式表进行合并(空)=""><> cout<<" *="" 7.退出=""><> cout<> ********************************************************" cin>>ch; switch (ch) { case 1: InitList(head); cout<<" 链表为："=""> showList(head); break ; case 2: cout<<" 链表为："=""> showList(head); break ; } case 3: cout<<" 删除的位置为:";="" cin="">>pos; Delete(head,pos); cout<<" 删除后链表为："="" ;="" showlist(head);="" break="" ;="" case="" 4:=""><<" 请输入插入的位置"="" ;="" cin="">>position; cout<<" 请输入插入的数据"="" ;="" cin="">>e; insert(head, position, e); cout<<" 插值后链表为："="" ;="" showlist(head);="" break="" ;="" case="" 5:=""><<" 链表长度为："="" ;="" length(head);="" break="" ;="" case="" 6:="" list="" *head1,*head2;="" head1="(List*)malloc(sizeof" (list));="" head2="(List*)malloc(sizeof" (list));=""><<" 依次递增的链表为："="" ;="" initlist(head1);=""><<" 依次递增的链表为："="" ;="" initlist(head2);="" mergelist(head1,head2);="" break="" ;="" case="" 7:="" return="" 0;="" break="" ;="" default="" :="" break="" ;="" }=""> 单链表的应用 (1)用单链表表示线性表的存储 (2)线性表的基本操作 :创建链表、销毁链表、插入、删除、判断是否为空链表、得到链表 长度、得到指定索引处的结点值、得到特定值所处链表位置以及打印链表。 @SuppressWarnings( public class LinkList //链表结点 private class Node { private T data ; //保存结点数据 private Node next ; //指向下一个结点的引用 public Node() { } public Node(T data,Node next) { this . data =data; this . next =next; } }//链表结点类定义结束 private Node header ; //头结点 private Node tail ; //我还定义了一个尾结点 可以不要 要它是为了在尾部插入元素方便 起见 private int size ; //结点数 //创建 默认构造方法 public LinkList() { header =null ; tail =null ; } //以指定元素初始化链表 只含一个元素 public LinkList(T element) { header =new Node(element,null ); tail =header ; size ++; } public int length() {//返回链表长度 return size ; } public T get(int index) {//返回指定索引处的结点值 return getNodeByIndex(index).data ; } private Node getNodeByIndex(int index) {//辅助 get()方法 if (index<0||index>size -1) { //此处我是抛出异常,在其他程序中我是输出错误提示并退出方法 throw new IndexOutOfBoundsException( } Node current = header ; for (int i=0;i if (i==index) { return current; } } return null ; //指定索引处元素不存在 } public int locate(T element) {//返回特定值位于链表的“位置”,虽然为位置可言 Node current=header ; //开始时,指向头结点 for (int i=0;i if (current.data .equals(element)) {//判断是否为所找元素 return i; } } return -1;//没找到 } //在指定位置处插入元素 public void insert(T element,int index) { if (index<0||index>size ) { //处理同上 throw new IndexOutOfBoundsException( } if (header ==null ) {//链表为空的情况 add(element); } if (index==0) {//要在表头插入元素 addAtHeader(element); } else { Node prev=getNodeByIndex(index-1); //这里是重点!!!先让新添加的结点的 next 指向 prev.next, 然后让 prev 的 next 指向新添加的元素 prev. next =new Node(element,prev.next ); size ++; } } } //链表尾部插入元素 public void add(T element) { if (header ==null ) {//空表 header =new Node(element,null ); tail =header ; } else { Node newNode=new Node(element,null ); tail . next =newNode;//在表尾插入元素时, tail 的作用显示出来了 tail =newNode; } size ++; } public void addAtHeader(T element) {//可以理解为作为 insert()方法的辅助 header =new Node(element,header ); if (tail ==null ) {//也说明在插入前链表还是空表 tail =header ; } size ++; } public T delete(int index) {//删除指定索引处的结点元素 if (index<0||index>size -1) { } Node del=null ; if (index==0) {//如果删除元素正好是头结点 del=header ; header =header . next ; //更新头结点 } else { //下面这段语句块是重点! Node prev=getNodeByIndex(index-1); del=prev.next ; prev. next =del.next ; del. next =null ; //调用此方法后, del 被回收 } size --; //元素个数减 1 return (T)del.data ; } public T remove() {//删除链表尾部的结点元素 return delete(size -1); } public boolean empty() {//判断链表是否为空 return size ==0; } public void clear() {//销毁链表 header =null ; tail =null ; size =0; } public String toString() {//重定义 toString()方法 if (empty()) { return } else { StringBuilder sb=new StringBuilder( for (Node current=header ;current!=null ;current=current.next ) { sb.append(current.data .toString()+ } int len=sb.length(); return sb.delete(len-1, len).append( } } public static void main(String[] args) {//测试 LinkList a.insert(1, 0);//表头插入元素 a.add(2);//表尾添加元素 a.add(3); System. out .println( a.insert(9, 1); System. out .println( System. out .println( System. out .println( System. out .println( System. out .println( a.clear(); System. out .println( } } (3)1. 结构定义: ADT List { 数据对象:D={ai|ai∈ ElemSet,i=1,2,…… ,n,n ≥ 0} 数据关系:R1={|ai-1,ai∈ D,i=2,…… ,n} 基本操作: Node(T data,Node next) 操作结果:为结点赋值,指定该结点所指向下一个结点的引用 LinkList(T element) 操作结果:以指定元素初始化链表 只含一个元素 length() 初始条件:链表已存在 操作结果:返回调用该方法的链表的数据元素个数 get(int index) 初始条件:链表已存在 操作结果:返回调用该方法的链表的第 index 数据元素的值 locate(T element) 初始条件:链表已存在 操作结果:返回调用该方法的链表的数据元素 element 是链表中的第几个数据 元素 insert(T element,int index) 初始条件:链表已存在 操作结果:在链表的第 index 位置处插入元素 element add(T element) 初始条件:链表已存在 操作结果:在链表尾部插入元素 element addAtHeader(T element) 初始条件:链表已存在 操作结果:在链表头部插入元素 element delete(int index) 初始条件:链表已存在 操作结果:删除链表中第 index 个数据元素并返回所删除的数据元素的值 remove() 初始条件:链表已存在 操作结果:删除链表表尾数据元素并返回所删除的数据元素的值 empty() 初始条件:链表已存在 操作结果:判断链表是否为空 , 返回 boolean 型结果 clear() 初始条件:链表已存在 操作结果:销毁链表 toString() 初始条件:链表已存在 操作结果:以插入顺序打印链表 }ADT List 2. 单链表的存储结构的定义: class LinkList private class Node {//链表结点 private T data ; //保存结点数据 private Node next ; //指向下一个结点的引用 public Node() { } public Node(T data,Node next) { this . data =data; this . next =next; } }//链表结点类定义结束 private Node header ; //头结点 private Node tail ; //我还定义了一个尾结点 可以不要 要它是为了在尾部插入元素方便 起见 private int size ; //结点数 } (4)基本操作: Node(T data,Node next) 为结点赋值,指定该结点所指向下一个结点的引用 LinkList(T element) 以指定元素初始化链表 length()返回调用该方法的链表的数据元素个数 get(int index)返回调用该方法的链表的第 index 数据元素的值 locate(T element)返回调用该方法的链表的数据元素 element 是链表中的第几个数据 元素 insert(T element,int index)在链表的第 index 位置处插入元素 element add(T element)在链表尾部插入元素 element addAtHeader(T element)在链表头部插入元素 element delete(int index)删除链表中第 index 个数据元素并返回所删除的数据元素的值 remove()删除链表表尾数据元素并返回所删除的数据元素的值 empty()判断链表是否为空 , 返回 boolean 型结果 clear()销毁链表 toString()以插入顺序打印链表 (5)应用没有实现 (6)实验结果: 五.单链表的应用 — 带头结点 链表的遍历: 访问链表每个元素一次且仅一次。 基本算法如下: void print(node *L) { P=L->next; while(P!=NULL) {visit(P->data); P=P->next; } } 例 设计算法,判断带头结点单链表 L 是否递增?若递增,则返回 ture ,否则返回 false 。 分析: (1)链表空,返回 true ; (2)只有一个元素,返回 true ; (3)每个元素都小于其直接后继,返回 true ; 否则,返回 false ; bool Judge(node *L) { node *P=L->next; if(P==NULL) return(1); while(P->next!=NULL) { if(P->data P=P->next; else return(0); } return(1); } 设计算法,使得带头结点的整型单链表中的所有元素值都变成原来的 3倍。 如:原 L=(1,2,3,4,5)变成 L’=(3,6,9,12,15) 2、双链表和双循环链表 (1)双链表 类型描述如下:prior data next typedef struct dnode {elementtype data; dnode *next,*prior; 引用:dnode *Head; } 插入 假设被插入位置的前一个结点的指针 P 已找到,插入由 S 指向的结点: ① S->next=P->next; ② S->prior=P; ③ P->next=S; ④ S->next->prior=S; 删除 假设被删除结点的指针 P 已找到,删除由 P 指向的结点: ① P->next->prior=P->prior; ② P->prior->next=P->next; ③ delete (P ) ; 顺序表: 逻辑上相邻的元素物理上也相邻 ; 可直接定位,节省搜索时间 然而,在 插入、删除时,需移动元素,浪费时间; 链表: 逻辑上相邻的元素物理上不一定相邻; 插入、删除时,不需移动元素。 §2.4 串 一、串的定义和运算 1、定义: 串 :是由 n 个字符 a1,a2,…,an 组成的有限序列(n ≥ 0) ,记作 S=“a1a2…an” 其中 n 为串长度, n=0时为空串; 注意:空串和空格串的区别: 空串 —— 没有元素; 空格串 —— 元素是空格符; 子串 :串 S 中若干个连续的字符组成的序列。 > 2、运算: (1)赋值(S=S1) :将一个串值 S1传送给一个串名 S ; (2)求长度 str_length(S):返回串 S 的长度值 ; (3)连接运算(S1+S2) :将 S1和 S2连接成一个新串; (4)求子串 substr (S,i,j ) :返回串 S 从第 i 个元素开始的 j 个元素所组成的子串 ; (5)串比较:比较两个串的大小 ; (6)插入运算 insert (S,i,S1) :将子串 S1插入到串 S 的从第 i 个字符开始的位置上 ; (7)删除运算 delete (S,i,j ) :删除串 S 中从第 i 个字符开始的 j 个字符 。 例 (1)空串和空格串 S1=“” ; S1是空串, S2=“ ” ; S2是空格串; (2)子串 S3=“abcde*$” ; S4=“bcd” ; S5=“abe” ; S4是 S3的子串; S5不是 S3的子串。 例 (1)赋值 S=“abcde*$” ; S1=“bcd” ; S2=S; 右边的值=>左边的串名。 (2)连接运算 已知:S1=“bcd” ; S2=“ace*” ; 则:S2+S1=“ace*bcd” (3)求子串 S=“abcde*$” ; substr(S,2,4)=“bcde” 例 (4)插入 已知:S=“abcde*$” ; S1=“bcd” ; S2=“kf” ; insert(S,4,“mn”)=“abcmnde*$” ; insert(S1,2,S2)=“bkfcde” (5)删除 S=“abcde*$” ; S1=“bcd” ; delete(S,5,2)=“abcd$” ; delete(S1,1,2)=“d” ; §3 栈、队列和数组 栈和队列都是运算受限的的线性表。下面我们分别讨论栈和队列的定义、基本运算和应用。 §3.1 栈 一、栈的定义和运算 1、定义: 栈 (Stack): 是只能在同一端插入和删除的线性表。 2、特点:后进先出(LIFO ) 。 3、栈的基本运算 (1)初始化栈: 建空栈; (2)判栈空: 若为空,则返回 true ,否则返回 false ; (3)判栈满: 若为满,则返回 true ,否则返回 false ; (4)读栈顶元素:取出栈顶元素。 条件:栈不空。 否则,应能明确给出标识,以便程序的处理 。 (5)入栈:将元素入栈,即放到栈顶。 如果栈满,怎样处理? (6)出栈:删除当前栈顶的元素。 如因为栈空而不能进行,应怎样处理? 二、顺序栈 1、存储结构: —— 采用顺序表来存储的栈; #define maxlen 最大容量 typedef struct seqstack {elementtype data[maxlen]; int top; } 引用:seqstack S; 栈顶元素是 data[top] 2、运算的实现 : (1)初始化 : void init_stack(seqstack &S) {S.top=-1;} (2)判栈空 : bool empty(seqstack S) {return (S.top==-1);} (3)判栈满:满返回 1,否则返回 0 bool stack_full(S); { if(S.top==maxlen-1) return(1); else return(0); (4)读栈顶元素 : void gettop(seqstack S,elementtype &x) { if(S.top==-1) error(“ 栈空 ”); else x=S.data[top]; } (5)入栈 : void push_stack(seqstack &S, elementtype x); { if(S.top==maxlen-1) error(“ 栈满 ”); else{ S.top++; S.data[S.top]=x ; } } (6)出栈 : elementtype pop_stack(seqstack &S); { if(S.top==-1) error(“ 栈空 ”); else{ S.top--; return(S.data[S.top+1]); } } 三、链栈 — 采用链表来存储的栈 1、类型描述 typedef struct node {elementtype data; node *next; } 引用 :node *top,*L; 四、栈的应用 1、栈的基本应用实例: 设栈的输入序列依次为 1,2,3,4,则所得的输出序列不可能是 __b____ 。 a 1,2,3,4 b 4,2,3,1 c 1,3,2,4 d 3,4,2,1 2、表达式的计算: 模拟表达式:12+5*6-4/2的求解过程。 #12+5*6-4/2# 操作数运算符 各自 依次入栈。 入栈规则:当前入栈的运算符 比栈顶的运算符优先级 高 。 2、 表达式的计算: 运算符优先级比较: ?* /? >?+ -? >?#? 3、递归与递归的阅读: (1)递归的定义: 如果一个函数在完成之前又调用自身,则称之为 递归函数 。 例 求整数 n 的阶乘函数 1 当 n=0时 n!= n*(n-1)! 当 n>0时 程序实现: int fact(int n) { if(n==0) return(1); else return(n*fact(n-1)); } (2)递归的一般形式: void fname(参数表 ) { if(数据作为递归出口 ) 简单操作 ; else{简单操作 ; fname(参数表 ); 简单操作 ; [fname(参数表 ); 简单操作 ;] //可能有多次调用 } } (3)递归的阅读: 例 void p(int n) { if(n>0) {cout<> p(n-1); } } 写出 p(3)的运行结果 结果:3 2 1 例 void p(int n) { if(n>0) {cout<> p(n-1); cout<> } } 写出 p(3)的运行结果 结果:3 2 1 1 2 3 课堂练习: void p(int n) { if(n>0) { p(n-1); cout<> p(n-1); } } 写出 p(3)的运行结果 结果:1 2 1 3 1 2 1 §3.2 队列 一、队列定义和运算 1、定义: 队列 (Queue) 是只能在这一端插入,另一端删除的线性表。 2、特点:先进先出(FIFO ) 3、运算: (1)初始化:设置队列为空; (2)判队空: 若为空,则返回 TRUE ,否则返回 FALSE ; (3)判队满: 若为满,则返回 TRUE ,否则返回 FALSE ; (4)取队头:取出队头元素; 条件:队列不空。 否则,应能明确给出标识,以便程序的处理。 (5)入队:将元素入队,即放到队列的尾部; 如果队列满,怎样处理? (6)出队:删除当前队头的元素。 如因为队列空而不能进行,应怎样处理? 二、顺序队列 1、类型描述: typedef struct seqqueue { elementtype data[maxlen]; int front,rear; } 2、顺序队列的讨论: (1)空队列:front==rear (2)满:rear==maxlen-1 假溢出 (3)入队:if(rear!=maxlen-1) (4)出队:if(front!=rear) {front++;x=data[front];} 3、循环队列: 讨论:数组空间为 maxlen=10 (1)空队列:front==rear → front==rear (2)队列满:rear=maxlen-1 → (rear+1)%maxlen==front 约定:保留一个元素空间。 (3)入队 : if((rear+1)%maxlen!=front) {rear=(rear+1)% maxlen;data[rear]=x;} (4)出队 : if(front!=rear) {front=(front+1)% maxlen;x=data[front];} (5)当前队头 : data[(front+1)%maxlen]; 思考 :若数组下标从 1开始,又将如何处理? rear(front) % maxlen+1 4、循环队列运算的实现: (1)初始化队列 : void init_queue(seqqueue &q); { q.front=0; q.rear=0; } (2)判队空 : bool empty(seqqueue q); {return(q.front==q.rear);} (3)判队满 : bool queue_full(seqqueue q) {return((q.rear+1)% maxlen==q.front);} (4)取队头:取出队头元素。 void front(seqqueue q, elementtype &x) {if(empty(q)) error(“ 队空 ”); else x=q.data[(q.front+1)%maxlen]; } (5)入队 : void inqueue(seqqueue &q,elementtype x) {if((q.rear+1)%maxlen==q.front; error(“ 队满 ”); else {q.rear=(q.rear+1)%maxlen; q.data[q.rear]=x;} } (6)出队 : void outqueue(seqqueue &q,elementtype &x) {if(q.front==q.rear) error(“ 队空 ”); else{q.front=(q.front+1)%maxlen; x=q.data[q.front];} } 三、链队列 1、类型描述: typedef struct linkqueue {node *front,*rear;} 引用:linkqueue Q; 2、运算的实现: (1)初始化队列 : void init_queue(linkqueue &q); { new(q.front); q.front->next=null; q.rear=q.front; } (2)判队空 : bool queue_empty(linkqueue q); {return(q.front==q.rear);} (3)取队头 : void queue_front(linkqueue q, elementtype &x) {if(empty(q)) error(“ 队列空 ”); else x=q.front->next->data; } (4)入队 : void inqueue(linkqueue &q,elementtype x) { new(s); s->data=x; s->next=null; q.rear->next=s; q.rear=s; } (5)出队 : void outqueue(linkqueue &q ,elementtype &x) {if(q.front==q.rear) error(“ 下溢出 ”); else{ u=q.front->next; q.front->next=u->next; x=u->data; delete(u); if(q.front->next==null) q.rear=q->front; } } §3.3 数组 一、数组定义和运算 1、定义: 数组 :有限个相同类型的变量组成的序列。 若每个变量是一维数组,则为 二维数组 ; 若每个变量是 n-1维数组,则为 n 维数组。 2、运算: (1)给定一组下标,存 /取数组元素的值; —— 计算元素的地址 (2)给定一组下标,修改相应的元素值。 二、数组的顺序存储 1、 行优先 存储: aij: 序号 num=(i-1)*n+j 地址 :addr=addr0+(num-1)*c (其中 c 是元素的 长度 ) 2、 列优先 存储: aij: 序号 num=(j-1)*m+i 地址 :addr=addr0+(num-1)*c (其中 c 是元素的长度 ) 例 数组 A[0..5,0..6]的每个元素占 5个单元, 将其按列优先次序存储在起始地址为 1000的连续的内存单元中, 则元素 A[5,5]的地址为 _1175_。 解 原矩阵是 A[0..5,0..6],且采用列优先存储, 则 A[5,5]的序号 num=5*6+6=36; addr=addr0+(num-1)*c=1000+35*5=1175。 三、矩阵的压缩存储 (一)特殊矩阵的压缩存储(行优先) : 1、对称矩阵 aij=aji aij: 序号 num=1+2+3+…+(i-1)+j 地址 :addr=addr0+(num-1)*c (其中 c 是元素的长度 ) 2、三角矩阵: a11, a21,a22, a31,a32,a33, … … … am1,am2, am3,… ,amn 思考:若是列优先存储又将如何处理? 3、三对角矩阵: a11,a12 a21,a22,a23 a32,a33,a34 … amn-1,amn aij:序号 num=[(i-1)*3-1]+(j-i+2) 地址 :addr=addr0+(num-1)*c (其中 c 是元素的长度 ) (二)稀疏矩阵的压缩存储: 数组中非零元素非常少,称为 稀疏矩阵 。 0 0 0 1 0 2 0 1 0 0 0 0 0 0 0 0 3 0 2 6 0 0 0 0 0 行 列 值 (1,4,1) (2,1,2) (2,3,1) 三元组 (4,2,3) (4,4,2) (4,5,6) (5,5,6) 《数据结构》实验报告 实验二、单链表的应用 专 业 ************* 班 级 ************* 学 号 ************* 学生姓名 ************* 指导老师 ************* *****************学院 ****年**月**日 一、实验目的 熟练掌握线性表的链式存储结构的建立方法以及基本操作算法，并根 据实际问题的要求，灵活运用。 二、实验内容 本次实验要求以班级学生信息作为管理对象，根据实验一建立班级学 生信息线性表的链式存储结构，并练习使用单链表的基本操作算法，实现 对班级学生信息的管理，包括学生信息的插入、学生信息的删除、学生信 息的查询和学生信息线性表的输出。 1、学生信息管理主控程序的设计 学生信息管理系统 ,,,,,,,,,,,,,,,,,,,,,,,, 1、学生信息线性表的建立 2、插入学生信息 3、查询学生信息 4、删除学生信息 5、输出所有学生信息 0、退出管理系统 ,,,,,,,,,,,,,,,,,,,,,,,, 请选择0,5: 2、学生信息管理功能函数的设计 (1) 设计函数createList(),建立学生信息单链表; (2) 设计函数printList(),输出学生信息单链表中的各项内容; (3) 设计函数insert(), 在学生信息单链表中插入新的学生信息结 点; (4) 设计函数findList(), 在学生信息单链表中实现按学号和姓名 两种方式查询学生信息; (5) 设计函数delNode()，在学生信息单链表中删除指定学生的信 息; 三、完成情况 #include #include #define MAXSIZE 100 typedef struct{ char num[8];/*学号*/ char name[9];/*姓名*/ char gender[3];/*性别*/ int score;/*成绩*/ }DataType; typedef struct { DataType stu; struct LinkList *next; }ListNode,*LinkList; int menu_select() { int sn; printf("\n 学生信息管理系统\n"); printf("=========================================\n"); printf(" 1.学生信息线性表的建立\n"); printf(" 2.插 入 学 生 信 息\n"); printf(" 3.查 询 学 生 信 息\n"); printf(" 4.删 除 学 生 信 息\n"); printf(" 5.输 出 所有学生信息\n"); 出 管 理 系 统\n"); printf(" 0.退 printf("==========================================\n"); printf("请选择0-5:\n"); for(;;) { scanf("%d",&sn); if (sn<0 ||="" sn="">5) printf("\n\t输入错误，重选0-5\n"); else break; } return sn; } LinkList createList() { int n,i; LinkList p,head; printf("有几位学生,请输入:\n"); fflush(stdin); scanf("%d",&n); printf("以下请输入这%d位学生的信息:\n",n); head=(LinkList)malloc(sizeof(ListNode)); head->next=NULL; for(i=n;i>0;i--) { p=(LinkList) malloc (sizeof(ListNode)); printf("\n学号(8) 姓名(8) 性别 成绩\n"); scanf("%s%s%s%d",&p->stu.num,&p->stu.name,&p->stu.gender,&p->stu. score); p->next=head->next; head->next=p; } return head; } void printList(LinkList L) { LinkList p; printf("\n学号(8) 姓名(8) 性别 成绩\n"); printf("-------------------------------------------\n"); p=L; p=p->next; while(p!=NULL) { printf("%s,%s,%s,%d\n",p->stu.num,p->stu.name,p->stu.gender,p->st u.score); p=p->next; } printf("--------------------------------------------------------- ---------\n"); } void insert(LinkList L,DataType *student,int i) { int j;LinkList s,p; p=L; j=0; while(L&& j if(!L|| j>i-1) printf("ERROR"); s=(LinkList*)malloc(sizeof(LinkList)); strcpy(s->stu.num,student->num); strcpy(s->stu.name,student->name); strcpy(s->stu.gender,student->gender); s->stu.score=student->score; s->next=p->next; p->next=s; } int findList(LinkList L) { char num[8]; char name[9]; int i=0,xz; LinkList p; p=L; printf("===========================\n"); printf("1、按学号查询\n"); printf("2、按姓名查询\n"); printf("===========================\n"); printf(" 请选择: "); fflush(stdin); scanf("%d",&xz); if (xz==1) { "); printf("请输入要查找学生的学号: scanf("%s",num); p=p->next; while(p!=NULL) { if(strcmp(p->stu.num,num)==0) { printf("您要查的学生为:\n学号(8) 姓名(8) 性别 成绩\n"); printf("-------------------------------------------\n"); printf("%s,%s,%s,%d\n",p->stu.num,p->stu.name,p->stu.gender,p->stu.sc ore); printf("------------------------------------------------------------- -----\n"); break; } } } else if (xz==2) { printf("请输入要查找学生的姓名:"); scanf("%s",name); p=p->next; while(p!=NULL) { if(strcmp(p->stu.name,name)==0) { printf("您要查的学生为:\n学号(8) 姓名(8) 性别 成绩\n"); printf("-------------------------------------------\n"); printf("%s,%s,%s,%d\n",p->stu.num,p->stu.name,p->stu.gender,p->stu.sc ore); printf("------------------------------------------------------------- -----\n"); break; } } } } void delNode(LinkList L) { int j; char i; LinkList q,p; DataType e; j=0; p=L; printf("请先查找您要删除的学生学号:"); scanf("%s",&i); p=p->next; while(strcmp(p->stu.num,i)!=0) { p=p->next; ++j; } if(!(p->next) || j>i-1) printf("ERROR"); q=p->next; p->next=q->next; e=q->stu; free(q); } void main() { DataType *student; int i; LinkList head; while(1){ switch(menu_select()) { case 1: printf("**************************************\n"); printf(" 学生信息线性表的建立 \n"); printf("***************************************\n"); head=createList(); break; case 2: printf("**************************************\n"); printf("添加学生信息\n"); printf("请输入要添加的学生信息:\n"); printf("\n学号(8) 姓名(8) 性别 成绩\n"); printf("**************************************\n"); student=(DataType *)malloc(sizeof(DataType)); fflush(stdin); scanf("%s%s%s%d",student->num,student->name,student->gender,&student->score); printf("请输入要插入的位置:\n"); fflush(stdin); scanf("%d",&i); insert(head,student,i); break; case 3: printf("**************************************\n"); printf("查询学生信息\n"); printf("**************************************\n"); findList(head); break; case 4: printf("**************************************\n"); printf("删除学生信息\n"); printf("**************************************\n"); delNode(head); break; case 5: printf("**************************************\n"); printf("输出所有学生信息\n"); printf("**************************************\n"); printList(head); break; case 0: printf("再见～\n"); getchar(); return; } } } 四、实验结果 1. 建立学生链表: 链表信息: 学号 姓名 性别 成绩 1001 LiSi M 90 1002 LiFang W 95 1003 WangWu M 89 2. 查询学生信息: 按学号查询(1) 输入要查找的学生学号:1003 屏幕显示: 1003，WangWu，M，89 3. 插入学生信息: 1004 LiChen W 92 插入位置:1 4. 输出所有学生信息: 1004，LiChen，W，92 1003，WangWu，M，89 1002，LiFang，W，95 1001，LiSi，M，90 五、问题与解决 六、思考题 七、实验总结 实验成绩 评分等评价项目 级 独立完成完整的实验内容，结果完全正确，报告内容完整，排版整洁美观，能A 真实体现实际操作过程及遇到的问题。 完成实验，实验内容较为完整，结果正确，报告内容较为完整，排版较为整洁B 美观，能体现实际操作过程及遇到的问题。 基本完成实验，结果正确，报告内容欠缺，排版较为整洁美观，能体现实际操C 作过程及遇到的问题。 不能独立完成完整的实验内容，结果不真实，报告内容欠缺，排版欠整洁美观，D 不能体现实际操作过程及遇到的问题。 南京信息工程大学 实验(实习)报告 实验(实习)名称 单链表的操作与应用 实验日期 2012/11/2 得分 指导教师 吴婷婷 系 计算机与软件学院 专业 网络工程 年级 2011 班次 1 姓名 管超 学号 20111346032 单链表的操作与应用 一、 实验目的 掌握线性表的单链表基本操作:建立、插入、删除、查找、合并、打印等运算。 二、 实验准备 1、 奔腾2计算机或以上机型 2、 Visual C++ 6.0 三、 实验内容 百货公司库中有一批电视机，按某价格从低到高的次序构成了一个单链表并存于计 算机中，链表的每一个结点指出同样价格的若干台。现在又有新到的m台价格为h 元的电视机入库。编写仓库电视机链表增加电视机的算法。 结点结构的定义为: typedef struct node { int number, price; struct node *next; }list; 四、 实验代码 #include #include #include typedef struct node { int number; int price; struct node *next; }List; //初始化链表 List* Init_func(List &L) { List *head; head = (List *)malloc(sizeof(List)); 1 if (head == NULL) { printf("无法分配空间!\n"); exit(0); } else { head->next = NULL; } return head; } //初始化数据 void InitData_func(List *head) { List *ptr, *previous, *current; ptr = (List *)malloc(sizeof(List)); if (ptr == NULL) { printf("无法分配空间!"); exit(0); } else { printf("\n请输入电视的价格: "); scanf("%d", &(ptr->price)); printf("请输入库存电视台数: "); scanf("%d", &(ptr->number)); } previous = head; current = head->next; while ((current != NULL) && (current->price < ptr-="">price)) { previous = current; current = current->next; } previous->next = ptr; ptr->next = current; 2 } //添加一个数据并进行整合 void Insert_func(List *head) { List *ptr, *previous, *current; int price, number; printf("\n请输入电视的价格: "); scanf("%d", &price); printf("请输入电视的台数: "); scanf("%d", &number); previous = head; current = head->next; if (current == NULL) { printf("\n库存中无电视, 正在为您添加数据...\n"); ptr = (List *)malloc(sizeof(List)); if (ptr == NULL) { printf("无法分配空间!\n"); exit(0); } else { ptr->price = price; ptr->number = number; } previous->next = ptr; ptr->next = current; printf("数据添加成功!\n"); } else { while ((current != NULL) && (current->price <= price))=""> { previous = current; current = current->next; } 3 if (previous->price == price) { printf("\n库存中有此价格电视, 正在为您归并...\n"); previous->number += number; printf("数据归并成功!\n"); } else { printf("\n库存中无此价格的电视, 正在为您添加数据...\n"); ptr = (List *)malloc(sizeof(List)); if (ptr == NULL) { printf("无法分配空间!\n"); exit(0); } else { ptr->price = price; ptr->number = number; } previous->next = ptr; ptr->next = current; printf("数据添加成功!\n"); } } } //显示链表中的数据 void Display_func(List *head) { List *current; current = head->next; if (current == NULL) { printf("库存中没有电视!\n"); } else { 4 printf("------------------------\n"); printf(" 价格 数量 \n"); while (current != NULL) { printf("%7d %8d\n", current->price, current->number); current = current->next; } printf("------------------------\n"); } } int main() { List television; List *head; int i, cnt; printf("初始化数据...\n\n"); head = Init_func(television); printf("初始化电视的种类(按价格, 小于10种): "); scanf("%d", &cnt); while (cnt > 10) { printf("种类过多, 请重新输入: "); scanf("%d", &cnt); } for (i=0; i { InitData_func(head); } printf("\n目前库存中的电视情况!\n"); Display_func(head); printf("\n现在添加一类电视...\n"); Insert_func(head); printf("\n现在库存中的电视情况!\n"); Display_func(head); 5 printf("操作结束!\n"); system("PAUSE"); return 0; } (图1:首先先初始化库存中的电视类别) (图2:初始化后显示库存中电视机的情况，并准备添加一新的电视种类) 6 (图3:当库存中没有此类电视时，添加后的情况) (图4:当库存中有此类电视时，添加后的情况) 五、 实验总结 这两次的上机实验，让我对顺序表的操作有了较深的理解。本次的单链表操作更为有点贴近生活，让操作增添趣味。我感触最深的就是在编写代码的时候，要首先有缜密的逻辑思维，对链表的操作要非常熟悉，特别是在指针的赋值和链表尾结点的判定上。 迫于时间，这两次的实验只是写了单纯的顺序表的操作，很多地方并没有对输入变量进行严格的判定，只是对内存动态分配上进行了严格的判定，所以程序的可靠性还是很差的～ 7 8范文二：单链表的应用
范文三：单链表的应用
范文四：单链表的应用
范文五：实验二 单链表的操作与应用
