第二章 线性表(10)

for(q=head,p=head->next; p!=0; q=p,p=p->next)if(q->data>p->data) return(0); return(1); 8．编写向类型为List的线性表L中第i个元素位置插入一个元素的算法，假定不需要对i的值进行有效性检查，同时不需要检查存储空间是否用完。

Void Insert(List& L，int i, ElemType x) 评分标准：请根据编程情况酌情给分。

vioid Insert(List& L,int i,ElemType x) {

for(int j=L.size-1;j>=i-1;j--) L.list[j+1]=L.list[j]; L.list[i-1]=x; L.size++; }

9．编写算法，求不带头结点的单链表的表表长。（7分） 已知单链表结点数据结构如下：

typedef struct node

{

int data;

struct node *next;

} LNode, *LinkList;

int length_LinkList(LinkList L) {

LNode *p=L;

int j = 0

while(p->next != NULL) { p = p->next; ++j; }

return j; }

10．编写算法，删除顺序表第i个元素。（8分） 已知顺序表的数据结构如下： typedef struct {

int data[100]; int last;

} SeqList;

int delete_SeqList(SeqList *L,int i) {

31

int j;

if (i <1 || i>L->last+1) {

printf(“不存在第i个元素”); return 0;

}

for (j=i; j<=L->L->last; ++j) { l->data[j-1] = L->data[j]; }

L->last--; return 1; }

11．编写算法查找不带头结点的单链表中的第i个结点，如找到返回1，否则返回0。（7分）

已知单链表结点数据结构如下：

typedef struct node

{

int data;

struct node *next;

} LNode, *LinkList;

LNode *Get_LinkList(inkList L, int i) {

LNode *p = L;

int j = 0;

while(p->next != NULL && j < i) { p = p->next; ++j; }

if (j == i) { return p; }

else {

return NULL; } }

12．编写算法，将任意十进制数转换成其他进制，要求写出完整代码，可采用顺序栈或链栈实现。（12分） #define Maxsize 100 typedef struct {

int data[Maxsize]; int top;

32

}SeqStack;

SeqStack *Init_SeqStack() {

SeqStack *s;

s=(SeqStack *)malloc(sizeof(SeqStack)); s->top=-1; return s; }

/*入栈*/

int Push_Seqstack(SeqStack *s,int x) {

if(s->top==Maxsize-1)return 0; else{

s->top++;

s->data[s->top]=x; return 1; } }

/*出栈*/

int Pop_SeqStack(SeqStack *s,int *x) {

if(Empty_SeqStack(s)) return 0; else{

*x=s->data[s->top]; s->top--; return 1; } }

/*判空栈*/

int Empty_SeqStack(SeqStack *s) {

if(s->top==-1) return 1; else return 0; }

void conversion(int N,int r) {

SeqStack *p; int y;

p=Init_SeqStack(); while(N) {

if(Push_Seqstack(p,N%r)==1) {N=N/r; } else

33

break; }

while(!Empty_SeqStack(p)) {

Pop_SeqStack(p,&y); printf(\ } }

void main() {

int M,t;

printf(\ scanf(\

printf(\ scanf(\ conversion(M,t); getch(); }

13．编写一算法完成瑟夫生死者游戏。（8分）

瑟夫生死者游戏的描述：N个旅客同乘一条船，因为严重超载，加上风浪大，危险万分；因此船长告诉乘客，只有将全船一半的旅客投入海中，其余人才能幸免遇难。无奈，大家只得同意这种办法，并拟定N个人围成一圈，由第一个人数起，依次报数，数到第r人，便把他投入海中，然后再从他的下一个人数起，数到第r人，再将他仍进海里，如此循环的进行，直到剩下N/2个乘客为止。问哪些位置是将被扔下大海的位置。

typedef struct node {

int data;

struct node *next; }ListNode,*LinkList;

LinkList CreateList(int n);

void DeleteNode(LinkList L,int n,int k); void PrintList(LinkList L); main() {

int n,k; LinkList H;

printf(\请输入总人数：\ scanf(\

printf(\请输入报数上限:\ scanf(\ H=CreateList(n);

34

DeleteNode(H,n,k); PrintList(H); getch(); }

LinkList CreateList(int n) {

int i;

LinkList L=NULL; ListNode *s,*R=NULL; for(i=1;i<=n;i++) {

s=(ListNode *)malloc(sizeof(ListNode)); s->data=i;

if(L==NULL) L=s; else R->next=s; R=s; }

if(L!=NULL) R->next=L; return L; }

void DeleteNode(LinkList L,int n,int k) {

int i,j=0;

ListNode *q,*p=L;

printf(\不幸投入大海的有：\ for(i=1;i<=n/2;i++) {

for(j=1;jnext; q=p->next;

p->next=q->next;

printf(\ if(i==0) printf(\ free(q); p=p->next; }

printf(\ L=p; }

void PrintList(LinkList L) {

35