《计算机软件基础》实验一
实验一：线性表／栈与队
一、实验目的
了解实现线性表／栈与队／数组所涉及到的数据结构。
二、实验要求
因受时间限制，从以下给出的4个实验内容中任选3个，分析并补齐给出的源程序，运行相应的程序，检验运行结果,以此巩固对相应部分的理论知识的理解。
1．复习线性表、栈与队列的定义，理解顺序存储、链式存储的方法及基本操作。
2．复习C语言中数组、指针及结构体的概念、定义方式。
3．上机前准备好全部源程序。
4．计算机中需要安装vc6.0或vs2010。
5．程序中所用结构体定义于datastru.h中。
三、实验内容
熟悉vs2010环境下建立程序源文件与调试程序的流程。
1、完成有序表(顺序表)中插入一元素并保证仍然有序。
……(补充程序)
void main( )
{
SEQUENLIST L;
int num,i,k,x;
L.last=0; //置顺序表为空,表长为0
printf("请输入顺序表元素，元素为整型量，用空格分开，-99为结束标志：");
/*输入顺序表元素,建立有序表,值从小到大*/
scanf("%d",&num);
while (num !=-99) {
………(补充程序)
L.last++;
scanf("%d",&num);
}
printf("%d",L.last);
printf("输入要插入的元素值(整型) : ");
scanf("%d",&num);
printf("\n插入前有序表元素列表 ：");
for (i=0; i printf("%4d",L.datas[i]); printf("\n"); k = L.last-1; while ((k>= 0) && (num k--; for(i=L.last-1; i>=k+1; i--) L.datas[i+1]=L.datas[i]; /*移动元素 */ L.datas[k+1]=num; /*新元素插入*/ L.last++; /*表长加1 */ printf("\n插入后有序表元素列表 ："); for (i=0; i printf("%4d",L.datas[i]); printf("\n"); } 2、完成链表的结点插入、删除操作，并显示操作前后的线性表中各元素的情况。 ……(补充程序) void inser_order(DATATYPE2 x, LINKLIST *head){ LINKLIST *pr, *pn, *pp; pr = head; pn = head->next; while(pn != NULL && pn->data < x) { ……(补充程序) } pp = (LINKLIST *)malloc(sizeof(LINKLIST)); ……(补充程序) } int count_head(LINKLIST *head) /*输出单链表元素值并计数*/ { int i = 0; LINKLIST *p; p = head->next; printf("输出单链表元素值 : "); while(p != NULL) { ……(补充程序) } printf("\n"); return i; } LINKLIST *creatlink_order_head(LINKLIST *head) /*建立带头结点的有序单链表*/ { LINKLIST *t, *p, *q; char ch; t = (LINKLIST *)malloc(sizeof(LINKLIST)); //建立带头结点的空链表 t->next = NULL; head = t; printf("单链表元素值为单个字符, 连续输入，#为结束字符 : "); while ((ch = getchar()) != '#') { ……(补充程序) } return head; } int main() { LINKLIST *head = NULL; int num; char ch; printf("\n 建立单链表\n\n"); head = creatlink_order_head(head); num = count_head(head); printf("单链表元素个数 = %d\n", num); fflush(stdin); printf("\n输入插入元素值 : "); ch = getchar(); inser_order(ch, head); printf("\n 元素插入后\n\n"); num = count_head(head); printf("插入后单链表元素个数 = %d\n", num); return 1; } 3、运用栈完成十进制数与八进制数的转换。 ……(补充程序) void initstack(SEQSTACK *s) /*顺序栈初始化*/ { ……(补充程序) } DATATYPE1 gettop(SEQSTACK *s) /*返回栈顶元素*/ { DATATYPE1 x; ……(补充程序) return x; } int push(SEQSTACK *s, DATATYPE1 x) /*元素x入栈*/ { if(s->top == MAXSIZE-1) { ……(补充程序) } else { ……(补充程序) return 1; } } DATATYPE1 pop(SEQSTACK *s) /*返回栈顶元素并删除栈顶元素*/ { DATATYPE1 x; if(s->top == 0) { printf("栈空\n"); x=0; } else { ……(补充程序) } return x; } int main( ) { SEQSTACK stack, *s; int n; s = &stack; initstack(s); n = 0; printf("输入一非负整数(十进制) ："); scanf("%d",&n); push(s,'#'); while(n != 0) { push(s, n % 8); /* %为求余数运算符, 余数入栈*/ n = n / 8; /* /为求整数商运算符,商不为零,继续运行*/ } printf("\n\n对应的八进制数为 ："); while(gettop(s) != '#') printf("%d",pop(s)); printf("\n"); return 1; } 4、实现带头结点链队元素的删除、插入操作，并显示操作前后的队列情况。 ……(补充程序) DATATYPE1 dellinkqueue(LINKQUEUE *q) /*删除队头元素并返回*/ { ……(补充程序) if(q->front == q->rear) { printf("队列空\n"); v = 0; } else { ……(补充程序) } return v; } void enlinkqueue(LINKQUEUE *q, DATATYPE1 x) /*元素x 入队列*/ { (q->rear)->next = (LINKQLIST *)malloc(sizeof(LINKQLIST)); ……(补充程序) } void initlinkqueue(LINKQUEUE *q) /*链队列初始化*/ { ……(补充程序) } void outlinkqueue(LINKQUEUE *q) /*链队列元素依次显示*/ { LINKQLIST *p; p = q->front; printf("队列元素显示 : "); while(p != q->rear) { ……(补充程序) } printf("\n"); } int main() { LINKQUEUE lq, *p; int j; p = &lq; initlinkqueue(p); printf("输入一整数(奇数——入队列、偶数——删除队头元素、0——退出) : "); scanf("%d", &j); while(j != 0) /*输入 0——退出*/ { if(j % 2 == 1) enlinkqueue(p,j); /*输入奇数——入队列*/ else j = dellinkqueue(p); /*输入偶数——删除队头元素*/ outlinkqueue(p); printf("\n输入一整数(奇数——入队列、偶数——删除队头元素、0——退出) : "); scanf("%d", &j); /*继续输入*/ } return 1; } 四、注意事项 注意程序中用到的结构体的来源及表示方法、调用方式。读懂程序结构，先补齐缺失代码，再调试运行程序。 五、实验总结和体会