数据结构用C语言描述资源-CSDN文库

需积分: 18 146 浏览量 2010-03-09 19:21:49 上传评论收藏 4.11MB DOC 举报

数据结构是计算机科学中至关重要的基础课程，它探讨如何有效地组织和管理数据，以便于高效地进行各种操作。本主题以C语言为编程工具，详细介绍了数据结构的概念和实现方法。这里我们将深入讨论《数据结构》一书中的部分知识点。在第一章“绪论”中，我们看到关于算法复杂度的讨论。算法的时间复杂度用来衡量算法运行所需时间与输入数据规模的关系。题目1.3中，给出了几个不同情况下的时间复杂度：(1) O(n)，线性时间复杂度，表示算法执行次数与数据规模成正比；(2) O(n^2)，平方时间复杂度，常见于两层嵌套循环；(3) O(n^1/2)，表示算法效率随数据规模的平方根增长；(4) O(logn)，对数时间复杂度，常见于二分查找等操作；(5) 的例子展示了当x和y相互抵消时，执行次数与y的大小成正比，即O(n)。第二章聚焦于“线性表”，线性表是一种基本的数据结构，包含一个有限序列的元素。书中提到了线性表的四种存储方式：顺序存储、单链表、双链表和静态链表。顺序存储使用数组实现，查找和修改元素速度快，但插入和删除元素需要移动大量元素。单链表每个节点包含数据和指向下一个节点的指针，插入和删除操作相对灵活，但随机访问效率较低。双链表则同时包含了前驱和后继指针，提供了双向遍历的能力。静态链表是在静态分配的内存区域中实现的链表，适用于内存资源有限的情况。对于线性表的操作，比如头指针是指向链表起始位置的指针，而头结点则是在首元素之前额外添加的节点，用于简化链表操作。头结点的数据域通常没有特殊含义，但它的指针域指向链表的第一个元素。另一方面，尾指针可以方便地访问链表的末尾。2.2中提到的只设尾指针的单循环链表，通过尾指针可以访问链表中的所有节点。 2.3的算法展示了如何在一个递增有序的向量中插入元素并保持有序。它首先查找插入位置，然后将所有大于新元素的元素向后移动一位，最后在正确的位置插入新元素。这个过程保证了向量的有序性。 2.4的算法则实现了向量的循环右移。通过使用一个临时变量存储开始位置的元素，并计算每次移动后下一个元素的下标，我们可以依次将元素向右移动k个位置。在这个过程中，我们需要一个计数器来跟踪已经移动的元素数量，确保所有元素都得到了正确处理。这些知识点构成了数据结构的基础，理解和掌握它们对于进一步学习高级算法和数据结构至关重要，同时也对实际的软件开发工作有着深远的影响。在C语言环境下，这些概念可以通过具体的代码实现，帮助我们更好地理解和运用数据结构。

资源推荐

资源详情

资源评论

http://www.zydg.net/computer/book/read/data-structure/

h971111102.html

习题解答(唐策善版)(其他版本在上面)

第一章绪论（参考答案）

1.3 (1) O(n)

(2) (2) O(n)

(3) (3) O(n)

(4) (4) O(n

1/2

)

(5) (5) 执行程序段的过程中，x,y 值变化如下：

循环次数 x y

0（初始） 91 100

1 92 100

2 93 100

…… …… ……

9 100 100

10 101 100

11 91 99

12 92 100

…… …… ……

20 101 99

21 91 98

…… …… ……

30 101 98

31 91 97

到 y=0 时，要执行 10*100 次，可记为 O（10*y）=O（n）

1.5 2

100

, (2/3)

log

n , n

1/2

3/2

, (3/2)

, n

log

, 2

n! , n

第二章线性表(参考答案)



在以下习题解答中，假定使用如下类型定义：

（1）顺序存储结构：

#dene MAXSIZE 1024

typedef int ElemType;// 实际上，ElemType 可以是任意类型

typedef struct

{ ElemType data[MAXSIZE];

int last; // last 表示终端结点在向量中的位置

}sequenlist;

（2）链式存储结构（单链表）

typedef struct node

{ElemType data;

struct node *next；

}linklist;

（3）链式存储结构（双链表）

typedef struct node

{ElemType data;

struct node *prior,*next；

}dlinklist;

（4）静态链表

typedef struct

{ElemType data;

int next;

}node;

node sa[MAXSIZE];



2.1 头指针：指向链表的指针。因为对链表的所有操均需从头指针开始，即头指针具有标

识链表的作用，所以链表的名字往往用头指针来标识。如：链表的头指针是 la，往往简称

为“链表 la”。

头结点：为了链表操作统一，在链表第一元素结点（称为首元结点，或首结点）之前增加

的一个结点，该结点称为头结点，其数据域不无实际意义（当然，也可以存储链表长度，

这只是副产品），其指针域指向头结点。这样在插入和删除中头结点不变。

开始结点：即上面所讲第一个元素的结点。

2.2 只设尾指针的单循环链表，从尾指针出发能访问链表上的任何结点。

2·3

void insert(ElemType A[],int elenum,ElemType x)

// 向量 A 目前有 elenum 个元素，且递增有序，本算法将 x 插入到向量 A 中，并保持向量

的递增有序。

{ int i=0,j;

while (i<elenum && A[i]<=x) i++; // 查找插入位置

for (j= elenum-1;j>=i;j--) A[j+1]=A[j];// 向后移动元素

A[i]=x; // 插入元素

} // 算法结束



2·4

void rightrotate(ElemType A[],int n,k)

// 以向量作存储结构，本算法将向量中的 n 个元素循环右移 k 位，且只用一个辅助空间。

{ int num=0; // 计数，最终应等于 n

int start=0; // 记录开始位置（下标）

while (num<n)

{ temp=A[start]; //暂存起点元素值，temp 与向量中元素类型相同

empty=start; //保存空位置下标

next=(start-K+n) %n; // 计算下一右移元素的下标

while (next !=start)

{ A[empty]=A[next];// 右移

num++; // 右移元素数加 1

empty=next;

next=(next-K+n) %n; // 计算新右移元素的下标

}

A[empty]=temp; // 把一轮右移中最后一个元素放到合适位置

num++;

start++; // 起点增 1，若 num<n 则开始下一轮右移。

}

} // 算法结束

算法二

算法思想：先将左面 n-k 个元素逆置，接着将右面 k 个元素逆置，最后再将这 n 个元素

逆置。

void rightrotate(ElemType A[],int n,k)

// 以向量作存储结构，本算法将向量中的 n 个元素循环右移 k 位，且只用一个辅助空间。

{ ElemType temp;

2·8

void union_invert(linklist *A,*B,*C)

// A 和 B 是两个带头结点的递增有序的单链表，本算法将两表合并成

// 一个带头结点的递减有序单链表 C，利用原表空间。

{ linklist *pa=A->next,*pb=B->next,*C=A,*r;

// pa,pb 为工作指针，分别指向 A 表和 B 表的当前元素，r 为当前逆置

//元素的后继指针, 使逆置元素的表避免断开。

//算法思想是边合并边逆置，使递增有序的单链表合并为递减有序的单链表。

C->next=null;//头结点摘下，指针域置空。算法中头指针 C 始终不变

while (pa && pb) // 两表均不空时作

if (pa->data<=pb->data) // 将 A 表中元素合并且逆置

{ r=pa->next; // 保留后继结点的指针

pa->next=C->next; // 逆置

C->next=pa;

pa=r; // 恢复待逆置结点的指针

}

else // 将 B 表中元素合并且逆置

{ r=pb->next; // 保留后继结点的指针

pb->next=C->next; // 逆置

C->next=pb;

pb=r; // 恢复待逆置结点的指针

}

// 以下 while (pa)和 while (pb)语句，只执行一个

while (pa) // 将 A 表中剩余元素逆置

{ r=pa->next; // 保留后继结点的指针

pa->next=C->next; // 逆置

C->next=pa;

pa=r; // 恢复待逆置结点的指针

}

while (pb) // 将 B 表中剩余元素逆置

{ r=pb->next; // 保留后继结点的指针

pb->next=C->next; // 逆置

C->next=pb;

pb=r; // 恢复待逆置结点的指针

}

free(B);//释放 B 表头结点

} // 算法结束



2·9

void deleteprior(linklist *L)

// 长度大于 1 的单循环链表，既无头结点，也无头指针，本算法删除*s 的前驱结点

{ linklist *p=s->next,*pre=s; // p 为工作指针，指向当前元素，

// pre 为前驱指针，指向当前元素*p 的前驱

while (p->next!=s) {pre=p; p=p->next;} // 查找*s 的前驱

pre->next=s;

free(p); // 删除元素

} // 算法结束



2·10

void one_to_three(linklist *A,*B,*C)

// A 是带头结点的的单链表，其数据元素是字符字母、字符、数字字符、其他字符。本算

法//将 A 表分成

// 三个带头结点的循环单链表 A、B 和 C，分别含有字母、数字和其它符号的同一类字符，

利用原表空间。

{ linklist *p=A->next,r;

// p 为工作指针，指向 A 表的当前元素，r 为当前元素的后继指针,使表避免断开。

//算法思想是取出当前元素，根据是字母、数字或其它符号，分别插入相应表中。

B=(linklist *)malloc(sizeof(linklist));//申请空间，不判断溢出

B->next=null; // 准备循环链表的头结点

C=(linklist *)malloc(sizeof(linklist));//申请空间，不判断溢出

C->next=null; // 准备循环链表的头结点

while(p)

{ r=p->next; // 用以记住后继结点

if (p->data>=’a’&&p->data<=’z’||p->data>=’A’&& p->data<=’Z’)

{p-> next=A->next; A->next=p;} // 将字母字符插入 A 表

else if (p->data>=’0’&&p->data<=’9’)

{p->next=B->next; B->next=p;} // 将数字字符插入 B 表

else {p->next=C->next; C->next=p;}// 将其它符号插入 C 表

p=r; // 恢复后继结点的指针

}//while

} // 算法结束

2·11

void locate(dlinklist *L)

// L 是带头结点的按访问频度递减的双向链表，本算法先查找数据 x,

// 查找成功时结点的访问频度域增 1，最后将该结点按频度递减插入链表中适当位置。

{ linklist *p=L->next,*q;

//p 为工作指针，指向 L 表的当前元素，q 为 p 的前驱，用于查找插入位置。

while (p && p->data !=x) p=p->next; // 查找值为 x 的结点。

if (!p) return (“不存在值为 x 的结点”);

else { p->freq++; // 令元素值为 x 的结点的 freq 域加 1 。

p->next->prir=p->prior; // 将 p 结点从链表上摘下。

p->prior->next=p->next;

q=p->prior; // 以下查找 p 结点的插入位置

while (q !=L && q->freq<p-freq) q=q->prior;

p->next=q->next; q->next->prior=p;// 将 p 结点插入

p->prior=q; q->next=p；

}

} // 算法结束

第三章栈和队列(参考答案)

// 从数据结构角度看，栈和队列是操作受限的线性结构，其顺序存储结构

// 和链式存储结构的定义与线性表相同，请参考教材，这里不再重复。

3.1 1 2 3 4 2 1 3 4 3 2 1 4 4 3 2 1

1 2 4 3 2 1 4 3 3 2 4 1

1 3 2 4 2 3 1 4 3 4 2 1

1 3 4 2 2 3 4 1

1 4 3 2 2 4 3 1

设入栈序列元素数为 n，则可能的出栈序列数为 C

=(1/n+1)*(2n!/(n!)

)

3.2 证明：由 j<k 和 p

说明 p

在 p

之前出栈，即在 k 未进栈之前 p

已出栈，之后 k 进

栈，然后 p

出栈；由 j<k 和 p

说明 p

在 p

之后出栈，即 p

被 p

压在下面，后进先

出。由以上两条，不可能存在 i<j<k 使 p

。也就是说，若有 1，2，3 顺序入栈，

不可能有 3，1，2 的出栈序列。

3.3 void sympthy(linklist *head, stack *s)

//判断长为 n 的字符串是否中心对称

{ int i=1; linklist *p=head->next;

while (i<=n/2) // 前一半字符进栈

{ push(s,p->data); p=p->next; }

剩余44页未读，继续阅读

评论收藏

内容反馈

supgenius

粉丝: 0
资源: 1

数据结构 用C语言描述

数据结构用C语言描述1

数据结构-用C语言描述

数据结构--用c语言描述

数据结构——用C语言描述

数据结构 C语言描述

《数据结构—用C语言描述》

数据结构（C语言描述） 严蔚敏

数据结构C语言描述课后答案（部分）+耿国华

数据结构（C语言描述）学习笔记、学习文档.zip

《数据结构（C语言描述）》电子教案

数据结构 C语言描述

数据结构用C语言描述

数据结构C语言描述

数据结构 c语言描述

数据结构——用C描述

《数据结构-C语言描述》全书代码学习.zip

数据结构--C语言描述-(耿国华)课后习题答案

数据结构 C语言描述 耿国华 高等教育出版社 课后习题答案

数据结构（c语言描述）

数据结构（C语言代码）.zip_数据结构用c语言描述第二版

数据结构c语言描述

数据结构c语言描述答案

数据结构-C语言描述 答案

数据结构课件--C语言描述

数据结构用C语言描述2

数据结构c语言描述第二版答案耿国华西安电子科技大学.docx

数据结构——C语言描述》耿国华

数据结构（C语言描述）电子版及其习题答案

数据结构-c语言描述

最新资源

数据结构用C语言描述

数据结构（C语言描述）严蔚敏

数据结构 C语言描述耿国华高等教育出版社课后习题答案

数据结构-C语言描述答案