《数据结构作业(18页).doc》由会员分享，可在线阅读，更多相关《数据结构作业(18页).doc（18页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、-数据结构作业-第 18 页#include#include#include#define NULL 0typedef struct Lnodeint data;struct Lnode *next;Lnode, *linkList;void createList(linkList *L,int n)Lnode *p, *q;int i;(*L) = (linkList)malloc(sizeof(Lnode);(*L)-next = NULL;q = (*L);for (i = 1; i data);q-next = p;q = p;p-next = NULL;void printout(l
2、inkList L)linkList p;p = L-next;while (p)printf(%d , p-data);p = p-next;void insert(linkList *L, int element, int w)linkList p,q;int j = 1; q=(*L)-next;p=(linkList)malloc(sizeof(Lnode); p-data=element;if(w=1)p-next=(*L)-next; (*L)-next=p;else while(q&jnext;j+;p-next=q-next;q-next=p;del(linkList *L,
3、int w)int element;linkList p;int j = 1;p = (*L)-next;if(w=1) (*L)-next=p-next;else while (j next;j+; element = p-next-data; p-next = p-next-next;return element;main()linkList L;int n, w,element;printf(input the number of List:);scanf(%d, &n); printf(input you datas:);createList(&L, n);printf(the dat
4、as are:);printout(L);printf(nthe data you want to insert:);scanf(%d, &element);printf(the location you want to insert:);scanf(%d,&w);insert(&L, element, w);printf(Now your list is:);printout(L);printf(ninput the location of you want to delete:);scanf(%d, &w);printf(the data of %d is delete!, del(&L,
5、 w);printf(nNow your list is:);printout(L);printf(n);system(pause);第二章作业一 选择题1下述哪一条是顺序存储结构的优点？（ A ）A存储密度大 B插入运算方便 C删除运算方便 D可方便地用于各种逻辑结构的存储表示2下面关于线性表的叙述中，错误的是哪一个？（ B ）A线性表采用顺序存储，必须占用一片连续的存储单元。B线性表采用顺序存储，便于进行插入和删除操作。C线性表采用链接存储，不必占用一片连续的存储单元。D线性表采用链接存储，便于插入和删除操作。3线性表是具有n个（ C ）的有限序列（n0）。 A表元素 B字符 C数据元素
6、D数据项 E信息项4若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。A顺序表 B双链表 C带头结点的双循环链表 D单循环链表5某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。A单链表 B仅有头指针的单循环链表 C双链表 D仅有尾指针的单循环链表6设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( D )最节省时间。A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表7若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个
7、结点。则采用（ D ）存储方式最节省运算时间。A单链表 B双链表 C单循环链表 D带头结点的双循环链表8. 静态链表中指针表示的是（ C ）. A 内存地址 B数组下标 C下一元素地址 D左、右孩子地址9. 链表不具有的特点是（ B ） A插入、删除不需要移动元素 B可随机访问任一元素 C不必事先估计存储空间 D所需空间与线性长度成正比10. 下面的叙述不正确的是（ BC ）A线性表在链式存储时，查找第i个元素的时间同i的值成正比 B. 线性表在链式存储时，查找第i个元素的时间同i的值无关C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比D. 线性表在顺序存储时，查找第i个元素的时
8、间同i的值无关12.(1) 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。 (2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。 (3) 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。以上错误的是（ B ） A（1），（2） B（1） C（1），（2）,(3) D.（2）13. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ C ）(1=ilink=head Bp-link=NILL Cp=NILL Dp= head17循环链表H的尾结点P的特点是（ A ）。 AP.NE
9、XT:=H BP.NEXT:= H.NEXT CP:=H DP:=H.NEXT18在一个以 h 为头的单循环链中，p 指针指向链尾的条件是（A） A. p-next=h B. p-next=NIL C. p-next-next=h D. p-data=-119完成在双循环链表结点p之后插入s的操作是（ D ）； A p-next:=s ; s-priou:=p; p-next-priou:=s ; s-next:=p-next;B p -next -priou:=s; p -next:=s; s -priou:=p; s -next:= p-next;C s -priou:=p; s -nex
10、t:=p-next; p-next:=s; p-next-priou:=s ;D s-priou:=p; s-next:=p-next; p-next-priou:=s ; p-next:=s;二、判断1. 链表中的头结点仅起到标识的作用。( ) /还可以使操作统一2. 顺序存储结构的主要缺点是不利于插入或删除操作。( ) 3线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。( )4顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。( )5. 对任何数据结构链式存储结构一定优于顺序存储结构。( ) 6顺序存储方式只能用于存储线性结构。( )7集合与线性表的区别在于是否按关
11、键字排序。( ) 8. 所谓静态链表就是一直不发生变化的链表。( ) 9. 线性表的特点是每个元素都有一个前驱和一个后继。( )10. 取线性表的第i个元素的时间同i的大小有关. ( ) 11. 循环链表不是线性表. ( ) 12. 线性表只能用顺序存储结构实现。( ) 13. 线性表就是顺序存储的表。( ) 14为了很方便的插入和删除数据，可以使用双向链表存放数据。( )15. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( )16. 链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结构中效率高。 ( ) 三、编写下列算法：1、 将两个单链表合并成一个单
12、链表。#include#define NULL 0typedef struct Lnode int data;struct Lnode *next;Lnode,*linkList;void createList(linkList *L,int n) /创建链表的函数 int i;linkList p,q;(*L)=(linkList)malloc(sizeof(Lnode);(*L)-next=NULL;q=(*L);for(i=1;idata);q-next=p;q=p; p-next=NULL;void combineLnode(linkList list1,linkList list2,
13、linkList *combineList) /合并链表的函数linkList p;*combineList=(linkList)malloc(sizeof(Lnode);p=*combineList;p-next=list1-next;while(p-next) p=p-next; p-next=list2-next;void printout(linkList list) /输出链表的函数linkList p;p=list-next; while(p) printf(%d ,p-data); p=p-next;main() linkList list1,list2,combineList;
14、int numList1,numList2;/创建链表list1printf(Please input the numbers of list1:);scanf(%d,&numList1);list1=(linkList)malloc(sizeof(Lnode);printf(Please input your datas:);createList(&list1,numList1); /创建链表list2printf(nPlease input the numbers of list2:);scanf(%d,&numList2);list2=(linkList)malloc(sizeof(Ln
15、ode);printf(Please input your datas:);createList(&list2,numList2);/将链表list1和list2进行合并操作 combineList=(linkList)malloc(sizeof(Lnode);combineLnode(list1,list2,&combineList);/输出合并后的链表combineListprintf(The datas after combine list1 and list2 are:n);printout(combineList);printf(n);2、 有一个有序单链表（从小到大），表头指针为h
16、ead，编写一个算法向该单链表中插入一个元素值为x的结点，使插入后该链表依然有序。#include#include#include#define NULL 0typedef struct Lnode int data;struct Lnode *next;Lnode,*linkList;int sort(int a,int n) int i,j,temp;for(i=0;in-1;i+)for(j=0;jaj+1) temp=aj;aj=aj+1;aj+1=temp;return a;int createRandNum(int n) int *randNum,i=0,temp;randNum=
17、(int *)malloc(sizeof(int)*n);srand(unsigned)time(NULL); while(i=1&tempnext=NULL;q=(*head);for(i=0;inext=NULL; p-data=randNumi; q-next=p; q=p;void insert(linkList *head,int value) linkList p,q;p=(*head)-next;q=(*head);while(p&p-datanext;q=q-next;p=(linkList)malloc(sizeof(Lnode);p-data=value;p-next=q-
18、next;q-next=p;void printOut(linkList head) linkList p;p=head-next;while(p) printf(%d ,p-data);p=p-next;printf(n);main() linkList head;int n,value;printf(Please input the numbers of datas:);scanf(%d,&n);createList(&head,n);printf(The original datas are:);printOut(head);printf(Please input your data y
19、ou want to insert:);scanf(%d,&value);insert(&head,value);printf(The new datas are:);printOut(head);3、 用算法是实现带头结点的单链表数据结点逆置。（原链表为a1，a2,an）（逆置后为：an,an-1,a2,a1）#includetypedef struct Lnode int data; struct Lnode *next;Lnode,*linkList;void createList(linkList *L,int n) linkList p;int i; (*L)=(linkList)m
20、alloc(sizeof(Lnode);(*L)-next=NULL;for(i=1;idata);p-next=(*L)-next;(*L)-next=p;void printOut(linkList p) if(p-next)printOut(p-next);printf(%d ,p-data);main()linkList head;int n;printf(Please input the number of datas:);scanf(%d,&n);printf(Please input your datas:);createList(&head,n);printf(Now the
21、datas you input are:);printOut(head-next);printf(n);3-1.c#include#includetypedef struct Qnode char data;struct Qnode *next;Qnode,*QueuePtr;typedef struct QueuePtr front;QueuePtr rear;linkQueue;void InitQueue(linkQueue *Q) Q-front=Q-rear=(QueuePtr)malloc(sizeof(Qnode);Q-front-next=NULL;void EnQueue(l
22、inkQueue *Q,char value) QueuePtr p;p=(QueuePtr)malloc(sizeof(Qnode);p-data=value;p-next=NULL;Q-rear-next=p;Q-rear=p;void operate(linkQueue *Q) QueuePtr p;while(Q-front-next) p=Q-front-next; /取出队头 printf(%c ,p-data); /输出队头的数据 EnQueue(Q,p-data); /队头入队列 deQueue(Q); /删除队头 deQueue(Q); /删除队头deQueue(linkQu
23、eue *Q) QueuePtr p;p=Q-front-next; /1.将队列的队头指针指向队列的第一个元素Q-front-next=p-next; /2.进行删除操作，将第二个队列元素赋给第一个元素if(Q-rear=p) /3.如果待删除的元素是最后一个元素，删除后队尾指针就不存在了，所以要将对头指针赋给队尾指针Q-rear=Q-front; free(p); /4.释放p所占用的空间main() linkQueue Q;InitQueue(&Q);EnQueue(&Q,A);EnQueue(&Q,B);EnQueue(&Q,C);EnQueue(&Q,D);operate(&Q);p
24、rintf(n);getchar();3-2.c#include#includetypedef struct SqNode int data; struct SqNode *next;SqNode,*QueuePtr;typedef struct QueuePtr rear;linkQueue;void InitSqueue(linkQueue *Q) Q-rear=(QueuePtr)malloc(sizeof(SqNode); Q-rear-next=Q-rear; /初始化头结点void EnQueue(linkQueue *Q,int value) QueuePtr p; p=(Que
25、uePtr)malloc(sizeof(SqNode); p-data=value; p-next=Q-rear-next; Q-rear-next=p; Q-rear=p;int DeQueue(linkQueue *Q) QueuePtr p; int value; p=Q-rear-next-next; value=p-data; if(Q-rear=Q-rear-next) return 0; if(p=Q-rear) Q-rear=Q-rear-next; Q-rear-next=p-next; Q-rear-next-next=p-next; free(p); return val
26、ue;main() linkQueue Q; int i,n,value; printf(Please input the number of Queue:); scanf(%d,&n); InitSqueue(&Q); for(i=1;i=n;i+) printf(Please input %dth data:,i); scanf(%d,&value); EnQueue(&Q,value); printf(The datas you input are:); while(value=DeQueue(&Q) printf(%d ,value); printf(n); getchar();1.GHDBEIFCA2.