内蒙古科技大学 经管学院 数据结构上机试题.doc

内 蒙 古 科 技 大 学数 据 结 构 原 理班级 09 信 管 1 班 学号 姓名 0 9 6 5 1 3 8XXX 成绩 一、 顺序表的操作（1）插入元素操作：将新元素x插入到顺序表a中第i个位置。（2）删除元素操作：删除顺序表a中第i个元素。#include#include #define LIST_INIT_SIZE 10#define LISTINCREMENT 10#define ERROR 0#define OK 1#define OVERFLOW -1typedef struct int *elem; int length; int listsize; SqList;int InitList(SqList *L) int i,k; L-elem=(int *)malloc(LIST_INIT_SIZE*sizeof(int); if(!L-elem) exit(OVERFLOW); L-length =10; L-listsize = LIST_INIT_SIZE; for(i=0;ilength;i+) scanf(%d,&k); L-elemi=k; return OK;int ListInsert(SqList *L,int i, int e) int *newbase,*q,*p; if(iL-length+1) return ERROR; if(L-length=L-listsize) newbase = ( int *)realloc(L-elem,( L-listsize +LISTINCREMENT)*sizeof(int); if(!newbase) exit(OVERFLOW) ; L-elem = newbase; L-listsize+=LISTINCREMENT; q=&(L-elemi-1); for(p=&(L-elemL-length-1);p=q;-p) *(p+1)=*p; *q=e; +L-length; return OK;int ListDelete(SqList *L, int i, int e) int *p, *q; if (iL-length) return ERROR; p = &(L-elemi-1); e = *p; q = L-elem+L-length-1; for (+p; plength; return OK; int display(SqList *L) int i; for(i=0;ilength;i+) printf(%d,L-elemi); printf( ); return OK;int main() SqList L; char e; int i,num; printf(请初始化10个元素：n);InitList(&L);printf(初始化后);display(&L);printf(n请输入你要删除的元素的位置n);scanf(%d,&i);ListDelete(&L,i,e);printf(删除后：n);display(&L);printf(n请输入插入位置和元素（格式“位置”，“元素”）);scanf(%d,%d,&i,&num);ListInsert(&L,i,num);printf(插入后：n);display(&L);return OK;二、单链表的操作（1）创建一个带头结点的单链表；（2）插入元素操作：将新元素x插入到单链表中第i个元素之后；（3）删除元素操作：删除单链表中值为x的元素；#include#include#define Null 0typedef int Element;typedef struct LNodeElement date;struct LNode *next;LNode,*LinkeList;LNode *Create(int n)int i;LNode *head,*now;head=(LNode*)malloc(sizeof(LNode);head-next=Null;for(i=0;idate);now-next=head-next;head-next=now;return head;int InsertNode(LNode*l,int i,Element e)LNode *now=l;int j=0;while(now&jnext;j+;if(!now|ji-1)printf(插入位置I不恰当！);return 0;LNode *s;s=(LNode*)malloc(sizeof(LNode);s-date=e;s-next=now-next;now-next=s;return 1;int DleteNode(LinkeList &l,int i)Element e;LNode*now,*d;int j=0;now=l;while(now-next&jnext;j+;if(!now|ji-1)printf();return 0;d=now-next;now-next=d-next;e=d-date;free(d);return e;void DisplayList(LinkeList &l)LNode * now;now=l-next;while(now!=Null)printf(%d ,now-date);now=now-next;void main()LNode *l;int num=0,ch=0;printf(输入链表长度:);scanf(%d,&num);printf(请输入个元素：n);l=Create(num);printf(初始化为：);DisplayList(l);printf(n请输入插入位置和元素（格式“位置”，“元素”）);scanf(%d,%d,&num,&ch);if(InsertNode(l,num,ch)printf(n插入后为:);DisplayList(l);printf(n请输入删除位置：);scanf(%d,&num);printf(n第%d个位置元素为“%d”n删除后为：,num,DleteNode(l,num);DisplayList(l);三、在顺序栈上实现将非负十进制数转换成二进制数。#include#include#define MAX 30typedef structint size;int *base,*top;SqStack;int InitStack(SqStack &s)s.base=(int *)malloc(MAX*sizeof(int);if(!s.base) return 0;s.top =s.base ;s.size =MAX;return 1;int Push(SqStack &s,int e)if(s.top-s.base s.size )s.base=(int*)realloc(s.base,(s.size +10)*sizeof(int);if(!s.base)return 0;s.top =s.base+s.size ;s.size +=10;*s.top +=e;return 1;int Pop(SqStack &s,int &e)if(s.base =s.top )return 0;e=*-s.top;return 1;void main()int num,k;SqStack l;InitStack(l);while(1)printf(请输入欲转换的十进制数！);scanf(%d,&num); while(num/2)!=0|(num)!=1)Push(l,num%2);num=num/2;Push(l,num%2);printf(转化结果为：);while(Pop(l,k)printf(%d,k);printf(n);四、在顺序表中采用顺序查找算法和折半查找算法寻找关键字X在顺序表中的位置。#include#include #define LIST_INIT_SIZE 10#define ERROR 0#define OK 1#define OVERFLOW -1#define TYPE inttypedef struct TYPE *elem; int length; int listsize; SqList;int InitList(SqList *L) int i; L-elem=(TYPE *)malloc(LIST_INIT_SIZE*sizeof(TYPE); if(!L-elem) exit(OVERFLOW); L-length =10; L-listsize = LIST_INIT_SIZE; for(i=0;ilength;i+) L-elemi=i*i; return OK;int SequanceSearch(SqList &l,int n, TYPE c)int i=1;int position;while(in)if(l.elem i-1=c)position=i;break;else position=-1;i+;if(position=n)return position;else return ERROR;int BinSearch(SqList &l,TYPE c)int low=0,mid,high=l.length ;while(low=high)mid=(low+high)/2;if(c=l.elem mid)return mid;elseif(cl.elem mid)high=mid-1;else low=mid+1;return ERROR;int display(SqList *L) int i; for(i=0;ilength;i+) printf(%d,L-elemi); printf( ); return OK;int main() SqList L; TYPE e; int i ; InitList(&L);printf(初始化顺序表为：);display(&L);while(1)printf(n顺序查找查什么？n);scanf(%d,&e);i=SequanceSearch(L,LIST_INIT_SIZE,e);if(i=ERROR)printf(顺序表没有该元素！n);else printf(所查元素所在位置为：%dn,i);printf(n折半查找查什么？n);scanf(%d,&e);i=BinSearch(L,e);if(i=ERROR)printf(顺序表没有该元素！n);else printf(所查元素所在位置为：%dn,i+1);return OK;五、将无序数列使用直接插入排序算法和快速排序算法将其排成递增有序数列。 #include #define MAX 15#define SWAP(x,y) int t; t = x; x = y; y = t; void Display(int a, int n) for (int i=0; in; i+) printf(%d ,ai); printf(n); void InsertSort(int a,int n) int i,j,temp; for (i=1; i=0 & temp aj; j-) aj+1 = aj; aj+1 = temp; Display(a, MAX); void QuickSort(int a,int low,int high) int z=0,y=0,k=0; if(low=high) z=low; y=high; k=az; do while(z=k)y-; if(zy)az =ay ; while(zy)&(az)k)z+; if(zy) ay =az ; Display(a,MAX); while(zy); az =k; QuickSort(a,low,z-1); QuickSort(a,z+1,high); void mai