6.
struct Node { int data ;
struct Node *next ; };
struct Node * delNode(struct Node *list , int n) { int flag = 1 , i = 1 ;
struct Node * p = list , *q = list->next ;
if(n == 1) { list = list->next ; free(p) ; return list ; }
while(q != NULL) { ++i ; if(i == n) { p->next = q->next ; free(q) ; q = p->next ; return list ; } q = q->next ; p = p->next ; }
return list ; } 7.
struct Node { int data ;
struct Node *next ; };
struct Node * fun(struct Node *list) {
struct Node * p = list , *q = list->next , * min , *pMin ; int temp ;
min = list ;
while(q != NULL) { if(q->data < min->data) { min = q ; pMin = p ;
} p = p->next ; q = q->next ; }
if(min != list) { pMin->next = min->next ; //删除最小节点 //将最小节点插入到list节点之后 min ->next = list->next ; list->next = min ; //交换list节点和min节点的值 temp = list->data ; list->data = min->data ; min->data = temp ; }
return list ; } 8.
struct Node { int data ;
struct Node *next ; };
struct Node * fun(struct Node *list) {
struct Node * p = list , *list2 = NULL , *q ;
struct Node *rear = (struct Node *) malloc(sizeof(struct Node)) ; //循环链表的尾指针
rear->next = rear ;
while(1) { q = p->next ; //保存下一个节点的地址 //头插法插入p p->next = rear->next ; rear->next = p ; p = q ; if(p == list) break ; }
return rear ; }
第九章
一、简答题
1、 不同：栈是先进后出，队列是先进先出
相同：都是线性结构，都有顺序实现和链式实现两种 2、不能得到4 3 5 6 1 2的出栈序列，原因如下 1. 1 2 3 4依次进栈 2. 4 3 出栈 3. 5入栈 4. 5出栈 5. 6入栈 6. 6出栈
此时栈中元素为1，2。所以若1一定在2之后出栈。
同样的分析方法，可知，1 3 5 4 2 6的出栈序列是可以的。 3、共占5 * 6 × 4 ＝ 120个字节
按行排序时，起始地址为1000 + 2*6 + 5 =1017
按列排序时，起始地址为 1000 + 5 * 5 + 2 = 1027 二、填空题 1、判栈满 添加元素 2、 判栈空 删除元素 3、 －1 m-1 4、空栈 空队 5、n-1 6、 1212 7、
三、改错题
1、这个说法是正确的 2、有存取限制
3、这个说法是正确的 4、 这个说法是正确的 5、练栈也是线性结构 四、单选
CBAC 5题的题意不清 BDCCA ABC
五、程序设计题 1.
#include
#define MAX 100
struct Stack {
int data[MAX] ; int top ; };
int pop(struct Stack * s) { if(s->top != -1)
return s->data[s->top--] ; else { printf(\ return -1 ; } }
int push(struct Stack *s , int n) { if(MAX -1 != s->top) return s->data[++s->top] = n ; else { printf(\ return -1 ; } }
int main() {
struct Stack s ; int i ;
s.top = -1 ;
for(i = 0 ; i < 10 ; ++i) push(&s , i) ; for(i = 0 ; i < 10 ; ++i) printf(\ return 0 ; } 2.
#include
#define MAX 100
struct Stack {
int data[MAX] ; int top ; };
//栈的出栈
int pop(struct Stack * s) { if(s->top != -1) return s->data[s->top--] ; else { printf(\ return -1 ; }
}
//栈的入栈
int push(struct Stack *s , int n) { if(MAX -1 != s->top) return s->data[++s->top] = n ; else { printf(\ return -1 ; } }
struct Stack s1 ; //模拟队列的入队的栈 struct Stack s2 ; //模拟队列的出队的栈
//初始化函数，使两个栈为空，使用模拟的队列时，要先执行该函数 void init() {
s1.top = s2.top = -1 ; }
//用栈模拟队列的入队 void enDeque(int data) { if(s1.top != MAX -1) push(&s1 , data) ; }
//用队列模拟出队 int ExDeque() { if(s2.top != -1) return pop(&s2) ; else { while(s1.top != -1) { push( &s2 , pop(&s1) ) ; } }
return pop(&s2) ; } 3.
#include
#define MAX 100
struct Stack {
char data[MAX] ; int top ; };