当前位置:首页 >> 理学 >>

数据结构与算法 第三章 简单数据结构new


第三章 简单数据结构

5/31/2010

1

第3章 简单数据结构
3.1 顺序表 3.2 链表 3.3 栈 3.4 队列 3.5 *广义表
5/31/2010 2

线性结构的特点
⑴ 存在唯一的被称为"第一个"的或"起 始"的数据元素; ⑵ 存在唯一的被称为"最后一个"的或 "终端"的数据元素; ⑶ 除第一个元素之外,集合中的每一个数 据元素均有且仅有一个前趋; ⑷ 除最后一个元素之外,集合中的每一个 数据元素均有且仅有一个后继.
5/31/2010 3

3.1 顺序表
3.1.1 线性表的基本概念 线性表是n(n≥0)个数据元素的有限序列,记为: L=(a1,a2,…,ai,…,an) 林鹏 (A,B,C,D,E,…Z)
字母表

黄龙 张艺谋 张三丰
登记表

5/31/2010

4

线性表的基本运算
⑴ 初始化setnull(L),建立一个空的线性表L; ⑵ 求表长length(L),函数返回L中的元素个数; ⑶ 取第i个元素get(L,i),其中1≤i≤length(L),否则 返回NULL; ⑷求前趋prior(L,x),返回元素x的前趋; ⑸求后继next(L,x),返回元素x的后继 ⑹定位locate(L,x),返回元素x在L中的位置,若x不 存在,返回0或NULL; ⑺插入元素x到第i个元素之前 insert(L,x,i),其中 1≤i≤length(L)+1,否则插入失败; ⑻删除第i个元素delete(L,i),其中1≤i≤length(L);
5/31/2010 5

3.1.2 线性表的顺序存储——顺序表
顺序表:用一组地址 连续的存储单元依次 存储线性表的元素, 用数组实现 例:(A,B,C,D,E,…Z)
线性表的第i个元素的存储地址为 Loc(ai)=Loc(a1)+(i-1)*k

A B C D E … Z
6

5/31/2010

顺序表数据类型的定义
//定义每一个结点,根据具体情况变化 typedef struct { int yinyu; //英语 int shuxue ;//数学 } elemtype; //定义顺序表 #define maxsize 1024 typedef struct { last=5 //顺序表最多容纳maxlen个元素 elemtp data[maxsize]; int last; // 指示当前表长 } sequenlist;
5/31/2010

英语

数学

89 78 98 66 55

90 68 55 77 88
maxlen

7

3.1.3 顺序表上的基本运算
(1)顺序表元素插入 操作的算法:
在第i个位置插入需移动次 数为n-i+1次,每个位置插入 的概率为1/(n+1) 平均移动次数: ∑(n-i+1)/(n+1)=n/2 (其中i=1..n+1) 算法的时间复杂度 T(n)=O(n)

A1 A2 … Ai … An-1 An

maxsize

5/31/2010

8

3.1.3 顺序表上的基本运算
(1)顺序表元素插入操作的算法: void insert(sequenlist *L,elemtype x,int i) {int j; if((i<1)||i>(L->last+1)) printf("插入位置不正确 插入位置不正确\n"); 插入位置不正确 else if(L->last>=MAXSIZE) printf("表已满,发生上溢 表已满, 表已满 发生上溢\n"); else {for(j=L->last;j>=i;j--) L->data[j+1]=L->data[j]; L->data[i]=x; L->last=L->last+1; } }/*insert*/

5/31/2010

9

3.1.3 顺序表上的基本运算
(2)顺序表元素删除操作的算法:
A1 A2 A3 … Ai … An
10

删除第i个元素需要移动n-i次 平均移动次数: ∑(n-i)/n (其中i=0..n-1) 算法的时间复杂度T(n)=O(n)

5/31/2010

3.1.3 顺序表上的基本运算
(2)顺序表元素删除操作的算法: void delete(sequenlist *L, int i) {int j; if((i<1)||(i>L->last)) printf("删除位置不正确 删除位置不正确\n"); 删除位置不正确 else {for(j=i+1;j<=L->last;j++) L->data[j-1]=L->data[j]; L->last=L->last-1; } }
5/31/2010 11

举例—删除顺序表中的重复元素
算法思路:从顺序表中第一个元素起,逐 个检查它后面是否有值相同的其它元素, 若有便删除之;直到表中所有元素都已无 重复元素为止.为此,算法中需设两重循 环,外层控制清除的趟数,内层控制每趟 的检查范围.

5/31/2010

12

举例—删除顺序表中的重复元素
void Purge(sequenlist *L) {int i,j,k; i=1; while(i<L->last)//每个元素都要比较 每个元素都要比较 {j=i+1; while(j<=L->last) if(L->data[j]==L->data[i])//相等则删除 相等则删除 {for(k=j+1;k<=L->last;k++) L->data[k-1]=L->data[k]; L->last=L->last-1;} else j++; i++;} delete(L, j) }/*Purge*/
5/31/2010 13

3.2 链表
顺序表存储的缺点 1)预先分配连续的空间 2)不能根据需要动态分配 3)插入删除等操作需要移动大量数据
H E L L O

5/31/2010

14

3.2 链表
单链表 循环链表 双向链表

5/31/2010

15

3.2.1单链表
单链表的组成及定义 数据域 指针域
结点组成 头指针 L H E

结点定义: 结点定义: typedef struct node { elemtp data; struct node *next; }LinkList;
5/31/2010

L L O

16

3.2.1单链表
头结点,头指针,第一个结点(首元结点)
头结点

head 头指针 H

第一个结点

E

L

L

O

5/31/2010

17

3.2.1单链表
动态生成一个结点 LinkList *H; H=(LinkList *) malloc(sizeof(LinkList)); 对结点中域的访问 H->elemtp和H->next 或 (*H).elemtp和(*H).next 释放结点占用的空间 free(H)

5/31/2010

18

3.2.2单链表上的基本运算
(1)单链表建立:
// 尾插法建表 :输入 个字符建立链表 直到输入为 结束 head 输入n个字符建立链表 直到输入为*结束 个字符建立链表,直到输入为 LinkList *CreateLinkList() {char ch; r LinkList *head;/*head为头结点指针 为头结点指针*/ 为头结点指针 p LinkList *r,*P; head=(LinkList *)malloc(sizeof(LinkList)); head->next=NULL; r=head; /*尾指针初始化 尾指针初始化*/ 尾指针初始化 ch=getchar(); while(ch!='*') /*"*"为输入数据结束符号 为输入数据结束符号*/ 为输入数据结束符号 { P=(LinkList *)malloc(sizeof(LinkList)); P->data=ch; P->next=NULL; r->next=P; r=r->next; ch=getchar(); } r return head; } p 思考:头插法建表怎么建?
5/31/2010

头结点

H E

L L O
19

3.2.2单链表上的基本运算
(2)求表长
int LengthLinkList(LinkList *L) {LinkList *P=L; int j=0; While(P->next!=NULL) {P=P->next; j++;} return j; /*返回表长 返回表长*/ 返回表长 }
head 头结点

H E

L L O

5/31/2010

20

(3)单链表元素的查找
//查找元素为 的结点 查找元素为X的结点 查找元素为 LinkList *LocateLinkList(LinkList *L, , elemtyPe x;) {LinkList *P; P=L->next; while((P!=NULL)&&(P->data!=x)) P=P->next; return P; /* 返 回 找 到 的 结 点 位 置 或 NULL*/ }/*LocateLinkList*/
5/31/2010 21

(3)单链表元素的查找
//查找第 个结点 查找第i个结点 查找第 LinkList *GetLinkList(LinkList *L,int i) {LinkList *P; int j=0; P=L; while((j<i)&&(P->next!=NULL)) {P=P->next; j++;} if(j==i) return P; else return NULL; }/*GetLinkList*/
5/31/2010 22

3.2.2单链表上的基本运算
(4)单链表元素插入操作
linklist_insert(linknode *L,int i,elemtp x)
L P

H

E q

L ②

L ①

O

w

5/31/2010

q=(LinkList *)malloc(sizeof(LinkList)); q->data=x;q->next=p->next; // 修改指针 p->next=q;

23

3.2.2单链表上的基本运算
(3)单链表元素插入操作
int linklist_insert(linknode *L,int i,elemtp x) { linknode *p, *q;int j=0;p=L; while ((p->next!=NULL) && (j++<i-1)) // 搜索到第i-1个结点 搜索到第 个结点 p=p->next; if (j==i-1) { q=(LinkList *)malloc(sizeof(LinkList));; // 建立新 结点 q->data=x; q->next=p->next; // 修改指针 p->next=q; return(1); } else return(0); // 插入位置无效 }
5/31/2010 24

3.2.2单链表上的基本运算
(5)单链表元素删除操作
linklist_del(linknode *L,int i)
L P

H

E

L

L

O

q=p->next; p->next=q->next; free(p);
5/31/2010 25

删除单链表L中的第i个结点算法
LinkList *deleteLinkList(LinkList *L,int i) {LinkList *P,*S; P=getLinkList(L,i-1);/*查找第 查找第i-1个结点 个结点*/ 查找第 个结点 if(P==NULL) Printf("第i-1个元素不存在 , 参数 有错 个元素不存在, 第 个元素不存在 参数i 有错\n"); else {S=P->next; P->next=S->next; free (S);} }*deleteLinkList*/ 该算法的时间复杂度为O(n) 该算法的时间复杂度为

5/31/2010

26

3.2.3循环链表和双向链表
1.循环链表
H

H

E

L 非空循环链表

L

O

H 空表

思考:如何判断是最后一个元素?如何判断是空表? 思考:如何判断是最后一个元素?如何判断是空表?
5/31/2010

head->next==head;

27

3.2.3循环链表和双向链表
2.双向链表 前驱 数据 后继
双链表结点格式

格式定义: typedef struct dbnode{ elemtp data; struct dbnode *prior,*next; }dblinknode;

L h 空表 L h e l

5/31/2010

28

双向链表
插入结点 将S结点插入P之前
p L

h ① ① S->prior=P->prior; ② S->next=P; ③ P->prior->next=s; ④ P->prior=S;

e ③ ④ A S ②

l

5/31/2010

29

双向链表
2.删除结点 思考:双向如何添加删除双链表结点
p L

h

e

l

p->piror->next=p->next; p->next->piror=p->piror; free(p);
5/31/2010 30

3.2.4两一元多项式相加的算法
已经两多项式A,B A=X -6X3 + 3X4 -6X5 B=1+5X3+6X5+9x6 求A+B;
格式定义:

系数 指数 next

typedef struct node { double coef; // 表示系数 int exp; // 表示指数 struct node *next; }polynode;

5/31/2010

31

多项式相加算法的思路
不产生新结点而利用原有结点空间,设两个指 针变量p和q分别指向A和B两个多项式单链表的 第一个结点,依次比较两指针所指结点的指数 项. 若指数相等系数相加,和不为零修改*p的系数 *p 项并删除*q,和为零删除*p和*q; 若指数不等,p->exp<q->exp时*p为和多项式中 的一项,p->exp>q->exp时把*q插在*p之前(*q 为和多项式中的一项); 所有操作之后要相应移动指针.直到其中一个 链空,把另一个链剩下的结点插在*p之后.
A B
5/31/2010

1 1 1 0

6 3 5 3

3 4 6 5

6 5 9 6
32

3.2.4两一元多项式相加的算法
void polyadd(polynomial *A,*B) {polynomial *p,*q,*s,*r; float x; p=A->next; q=B->next; s=A; while((p!=NULL)&&(q!=NULL)) if((p->exp)>(q->exp)) {r=q->next; q- next= /*把 接在q 所指结点后*/ q - > next = p ; /* 把 p 接在 q 所指结点后 */ s- next= /*把 接入结果链*/ s - > next = q ; /* 把 q 接入结果链 */ s=q; q=r;} else if(p->exp<q->exp) {s=p; p=p->next; } else { x=p->coef+q->coef; if(x!=0) {p->coef=x; s=p; } else {s->next=p->next; free(p);} p=s->next; r=q; q=q->next; free(r);

A B
5/31/2010

1 1 1 0

6 3 5 3

3 4 6 5

6 5 9 6
33

3.3栈(stack)
3.3.1栈的概念及运算 栈:限制仅在一端对元素插入或删除操作的线 性表
出栈 入栈

是先进后出,后进 是先进后出, 现出的一种结构

栈顶

栈底
5/31/2010

a5 a4 a3 a2 a1
34

3.3.1栈的概念及运算
栈的基本运算: (1) 置空栈 setnull(S) 建立空栈S; (2)判栈空 empty(S) (3) (3)入栈 push(S,x) 将元素x压入栈S中(插入), x S 使之成为新的栈顶元素,成立的条件是栈未满; (4)出栈 pop(S) 弹出栈顶元素(返回栈顶并删 除),成立的条件是栈非空; (5)取栈顶元素 gettop(S) 返回非空栈的栈顶元素 的值;

5/31/2010

35

3.3.2 顺序栈及运算实现
顺序栈:利用顺序存储结构实现的栈,用 一数组实现 数据类型: top typedef struct{ a5 a4 elemtp data[maxlen]; a3 int top; // 栈顶指针 a2 }sqstack;
a1
5/31/2010 36

3.3.2 顺序栈及运算实现
运算实现 (1)顺序栈的初始化: void setnull(sqstack *S) { S->top = -1; } 说明栈为空
Top=-1
5/31/2010 37

3.3.2 顺序栈及运算实现
运算实现
(2)进栈算法: int push(sqstack *S,elemtp x) { if (S->top>=maxlen-1) return(0); // 栈已满或溢出 S->top++ S->data[S->top] = x; return(1); } a6
top

a5 a4 a3 a2 a1
38

5/31/2010

3.3.2 顺序栈及运算实现
运算实现 (3)顺序栈的元素出栈: elemtp pop (sqstack *S) { if (S->top==-1) return NULL; // 栈已空 else {S->top--; return (S->data[S->top]); } }
5/31/2010

Top

a5 a4 a3 a2 a1
39

3.3.3 链栈及运算实现
只能在链头进行操作的单链表 TOP 链栈的数据类型: typedef struct node { elemtp data; struct node *next; }linkstack;
5/31/2010

A5 A4

A3 A2 A1

40

3.3.3 链栈及运算实现
(1)链栈的初始化: void init_linkstack(linkstacknode *t) { t=NULL; }

5/31/2010

41

3.3.3 链栈及运算实现
(2)链栈的元素入栈: void push (linkstack *top,elemtp x) { linkstack *p p=new linkstack; // 建立新的 结点 p->data=x; p->next=top; t=top; // 修改栈顶指针 }
5/31/2010

A5 TOP A4

A3 A2 A1

42

3.3.3 链栈及运算实现
(3)链栈的元素出栈: elemtp pop (linkstack *t) { linkstack *p; elemtp x; if (t==NULL) return NULL; // 链栈已空 x=t->data; p=t; t=t->next; // 修改栈顶指针 delete p; // free(p); 释放原栈顶结点 return(x); }
TOP

A5 A4

A3 A2 A1

5/31/2010

43

3.3.4 栈的应用举例
递归算法的实现 递归算法的执行过程实际上应用了栈 例:求阶层函数
1 N=0 F(N)= F(N-1)*N N>=1

5/31/2010

44

3.3.4 栈的应用举例
递归算法的实现 例:求阶层函数 int fact(int n) {if(n==0) return 1; else return n*fact(n-1); }

F(1) F(2) … F(N-3) F(N-2) F(N-1)
45

5/31/2010

3.3.4 栈的应用举例
递归算法的实现 例:求阶层函数,改写成用栈实现 int fact(int n) {sqstack s; int rs=1; if (n==0)return 1; while(n>0)//入栈 {push (&s,n);n--} while(stack.top!=-1) //出栈 rs=pop (&s)*rs; return rs; } 5/31/2010
1 2 … N-2 N-1 N
46

3.4队列
3.4.1 队列的概念及其运算 队列:先进先出的线性表,仅限于表的一端进 行元素的插入和表的另一端进行元素的删除操 作.

队头 出队(删除) 出队(删除)

队尾 入队插入

a1 a2 a3 a4 a5

5/31/2010

47

3.4.1 队列的概念及其运算
1. 2. 3. 4. 5. 6. 7.

队列的基本运算: 初始化队列 init_queue(q),建立空队列q; 入队列 in_queue(q,x),元素x在对尾插入队列; 出队列 out_queue(q),若q非空队列,取出对头元素, 并在队列中删除,对头指针指向下一个元素; 判对列空 empty_queue(q),队列中是否无元素; 求队列长度 length_queue(q),返回队列中的元素个数; 取对头元素 getfront_queue(q),读取对头元素数据; 置队列空 clear_queue(q),删除队列中所有元素,使 对长为0.

5/31/2010

48

3.4.2 顺序队列及运算实现
如同顺序表,用一维数 组存放队列元素数据.
顺序队列的类型定义如下: 顺序队列的类型定义如下: #define maxlen maxsize typedef struct { elemtp data[maxlen]; int front,rear; // 分别指示 队头和队尾元素的下标 } sequeue;
rear

a5 a4 a3 a2

front

5/31/2010

49

3.4.2 顺序队列及运算实现
(1)初始化队列: void init_cycque(sequeue &q) { q->front=q->rear=-1; }

4 3 2 1 0 front rear

5/31/2010

50

3.4.2 顺序队列及运算实现
(2)入队
int in_que(sequeue *q,elemtp x) { if (q->rear+1==maxsize) return(0); q->data[++q->rear]=x; return(1); }
rear

a6 a5 a4 a3 a2

Front=0
5/31/2010 51

3.4.2 顺序队列及运算实现
(3)出队
elemtp out_que(sequeue *q) { if (q->rear==q->front) //空 return(0); //否则 return q->data[++q->front]; }
rear

a6 a5 a4

a3
Front=1

5/31/2010

52

3.4.2 顺序队列及运算实现
队列假溢出
front Maxsize-1

思考: 思考: q->rear==q>front==maxsize-1时, 时 队列真的为满吗? 队列真的为满吗?

rear

5/31/2010

53

3.4.2 顺序队列及运算实现
循环队列
将顺序队列的首尾相连, 即:q->data[maxsize-1] 后紧跟q->data[0]
rear a3 3 4 5 6 a2 2 1 a1 0 7 front

rear
5/31/2010 54

3.4.2 顺序队列及运算实现
循环队列 :几种状态的判断
3 4 5 6 7 front rear 队列空 Q.front==Q.rear==k
5/31/2010

2 1 0

a3 3 a4 4 a5 5 6 a6

a2 2 1 a1 0 7 a7 rear front

队列满 (Q.rear+1) % maxlen==Q.front
55

3.4.2 顺序队列及运算实现
(1)初始化循环队列: void init_cycque(cyclicqueue &q) { q.front=q.rear=0; } 3 2
4 5 6 7 front rear 1 0

5/31/2010

56

3.4.2 顺序队列及运算实现
(2)循环队列的元素入队操作的算法: int in_cycque(cyclicqueue &q,elemtp x) { if ((q.rear+1) % maxlen==q.front) return(0); // 队满 q.rear=(q.rear+1) % maxlen; data[q.rear]=x; return(1); }
5/31/2010 57

3.4.2 顺序队列及运算实现
(3)循环队列的元素出队操作的算法: elemtp out_cycque(cyclicqueue &q) { if (q.front==q.rear) return NULL; // 对空 q.front=(q.front+1) % maxlen; return(data[q.front]); }

5/31/2010

58

3.4.3 链队列及运算实现
链队列的数据类型定义: typedef struct node { elemtp data; struct node *next; } linknode ; // 元素结点类型 typedef struct {linknode *front,*rear; }linkqueue; // 队头和队尾指针结构 linkqueue Q; // 队列变量
front rear 头结点 h L L O

5/31/2010

当Q.front==Q.rear时,表示队列为空 时

59

3.4.3 链队列及运算实现
(1)链队列的初始化:
void iniqueue(linkqueue *q) {q->front=(linknode *)malloc(sizeof(linknode)); q->rear=q->front; /*让尾指针也指向 让尾指针也指向 头结点*/ 头结点 q->front->next=NULL; /* 填 头 结 点 的 next域为 域为NULL*/ 域为 front }
rear 头结点

5/31/2010

60

3.4.3 链队列及运算实现
(2)链队列的入队算法: void addqueue(linkqueue *q,elemtype x) { linknode *p; p=(linknode *)malloc(sizeof(linknode)); p->data=x; /*填入元素值 填入元素值*/ 填入元素值 p->next=NULL; /*指针域填 指针域填NULL值*/ 指针域填 值 q->rear->next=p; /*新结点插入队尾 新结点插入队尾*/ 新结点插入队尾 q->rear=p; /*修改队尾指针 修改队尾指针*/ 修改队尾指针 }

5/31/2010

61

3.4.3 链队列及运算实现
(3)链队列的出队算法: elemtype outqueue(linkqueue *q) {linknode *p; if(q->rear==q->front) return NULL; /*队列为空时返回 队列为空时返回NULL*/ 队列为空时返回 else {p=q->front; /*p指向头结点 指向头结点*/ 指向头结点 q->front=q->front->next; free (p); return q->front->data; } }
5/31/2010 62

3.3.4队列的应用
(1)数据的输入/输出处理中的数据缓冲, 如键盘缓冲区,打印缓冲区,文件缓冲区 等 (2)实时数据采集时的平均值计算,如电 子称的数据采集和显示处理(阻尼算法) (3)消息队列(Windows) (4)离散事件模拟

5/31/2010

63

3.5广义表
3.5.1 广义表的概念 广义表 是线性表的一种推广,它的数 据元素不仅可以是一个数据元素,还可以 是表本身. 通常记做:LS=(d1,d2,d3…,dn) 例: LS=(a, (b,c,d) ,e) 或LS=(a,LB,e) LB=(b,c,d)

5/31/2010

64

3.5.1 广义表的概念
广义表的一些例子: 1)A=() A是一个空表,长度为0,深度为1 2)B=(e) 列表B只有一个单元素e,表长度为1, 深度为1 3)C=(a,(b,c,d)) 3 C=(a,(b,c,d)) 列表C的长度为2,两个元素 C 2 分别为单元素a和子表(b,c,d),列表的深度为2 4)D=(A,B,C) 列表D的长度为3,三个元素都是列 表,即有D=((),(e),(a,(b,c,d))) 5)E=(a,E) E是一个递归的表,它的长度为2,展 开后相当于一个无限的列表E=(a,(a,(a,...)))
5/31/2010 65

广义表的基本操作(运算)
(1)求广义表的长度len(LS) 表中元素的个数,不包括子表中的元素个数 例:A=(a, (b,c,d) ,d) B=(f,)

5/31/2010

66

广义表的基本操作(运算)
(2)求广义表的深度 展开后括号的层次 例:A=(a, (b,c,d) ,d) B=(f,A)

5/31/2010

67

广义表的基本操作(运算)
(3)求表头 (4)求表尾 表尾一定是个广义表 如:LB=(a),tail(LB)=() LC=(a,(b,c)),tail(LC)=(b,c)

l

5/31/2010

68

3.5.2 广义表的存储结构及运算实现
广义表的数据类型定义: typedef struct node next { int atom; atom data/snext struct node *next; union{ elemtp data;/*atom=1时为数据*/ struct node *snext;/*atom=0时为子表*/ }elemdata; }glist;
5/31/2010 69

3.5.2 广义表的存储结构及运算实现
例:画出如下广义表的存储表示 Ls=((()),a,(b,c),((d)),e)
0 0 1 a 0 1 1 b c 0 0 1 d 1 e

5/31/2010

70

3.5.2 广义表的存储结构及运算实现
(1)求广义表深度的递归算法: )求广义表深度的递归算法: int depth(glist *LS) {glist *p; int dep,max; , ; max=0; /*max为当前最大深度 为当前最大深度*/ ; 为当前最大深度 p=LS->next ; while(p!=NULL) {/* 判断所指结点是否为子表 判断所指结点是否为子表*/ 所指结点是否为子表 if(p->atom==0) {dep=depth(p->snext); ; if(dep>max) max=dep ; } p=p->next; ; } return max+1; }

L

1 a

0 1 b

0 0 0 c

5/31/2010

71

小结
顺序表:用数组表示元素 顺序表 用数组表示元素 链表:单链表,循环链表,双向链表; 链表:单链表,循环链表,双向链表;一 元多项式的加法 顺序栈,链栈; 栈:顺序栈,链栈;递归调用 队列:顺序队列(循环队列),链队列; ),链队列 队列:顺序队列(循环队列),链队列; 广义表:存储结构 广义表 存储结构

5/31/2010

72

typedef关键词 typedef关键词
格式 typedef 已有类型 新定义类型; 例如: 例如: typedef int count; count x,y;

5/31/2010

73

struct结构体 struct结构体
结构体(structure)是一种数据类型, 结构体(structure)是一种数据类型, 它把互相联系的数据组合成一个整体.例,

5/31/2010

74

一个学生的学号,姓名,性别,年龄,成绩, 地址,是互相联系的数据,在C 地址,是互相联系的数据,在C语言中用"结构 体(structure)"来定义. 体(structure)"来定义.

struct student { int num; char name[20]; char sex; int age; float score; char addr[30]; };
5/31/2010

/* 学号 */ /* 姓名 */ /* 性别 */ /* 年龄 */ /* 成绩 */ /* 地址 */
75

一,先定义结构体类型,再定义变量 例, struct student { int num; char name[20]; char sex; int age; float score; char addr[30]; }; struct student student1, student2;

5/31/2010

76

二,在定义类型的同时定义变量
struct student { int num; char name[20]; char sex; int age; float score; char addr[30]; }student1, student2; student2;
5/31/2010 77

三,直接定义变量
struct { int num; char name[20]; char sex; int age; float score; char addr[30]; }student1, student2; student2;
5/31/2010 78

四,成员是另一个结构体变量
struct date { int month; int day; int year; }; struct student { int num; char name[20]; char sex; int age; struct date birthday; char addr[30]; } student1, student2; student2;
5/31/2010 79

结构体变量的引用
引用结构体成员的方式: 结构体变量名. 结构体变量名.成员名 例: ①student1.age=20; ②printf("%d,%s,%c,%d,%f,%s", student1.num, student1.name, student1.sex,student1.age, student1.score, sutdent1.addr); ③scanf("%d", &student1.age);

5/31/2010

80

结构体数组
一,结构体数组的定义 struct student { int num; char name[20]; char sex; int age; float score; char addr[30]; }; struct student stu[3];

5/31/2010

81

指针
一,指针变量的定义
指针变量定义的一般形式: 类型标识符 * 标识符 例, int i,j; i=3;j=6; int *pointer_1; 指针变量的赋值: 二,指针变量的赋值: 例 pointer_1 &i; pointer_1 = &i; *pointer_1 100;//相当于 100 *pointer_1 = 100;//相当于i=100 相当于i=
5/31/2010 82

也可以在定义指针变量的同时指定其初值, 也可以在定义指针变量的同时指定其初值, 如: int a; int *p = &a; *p=100 p = 100;

5/31/2010

83

二,指针变量的两个运算符
有两个运算符可以引用指针变量: (1)&:取地址运算符.如 pointer_1 = &i; (2)*:指针运算符. 用于访问指针变量所指向的变量. *和&是互逆运算 例; i=3; ptr=&i; *ptr=15;
5/31/2010

直接访问

间接访问等同于i=15 间接访问等同于
84

指针作为函数参数
void swap(int x,int y) { int temp; temp=x; x=y; y=temp; } void swap(int *x,int *y) { int temp; temp=*x; *x=*y; *y=temp; }

5/31/2010

85

结构体指针
struct student { long int nnum; char name[20]; char sex; float score; }; struct student stu_1; struct student *p; p = &stu_1;
5/31/2010 86

结构体指针,通过指向运算符-> 结构体指针,通过指向运算符->引用结 构体中的成员.例, p->num p->name p->sex p->score 因此结构体成员的引用方式有以下三种: 结构体变量. 结构体变量.成员名 (*p).成员名 (*p).成员名 p->成员名
5/31/2010 87

函数指针

5/31/2010

88


相关文章:
第三章 简单数据结构new_图文.ppt
第三章 简单数据结构new_工学_高等教育_教育专区。算法与数据结构ppt 第三章 简单数据结构 1/6/2011 1 第3章 简单数据结构 3.1 顺序表 3.2 链表 3.3 栈...
数据结构算法(第三章).doc
数据结构算法(第三章) - ∥构造一个空栈 S Status InitStack
数据结构与算法__第三章_清华大学出版社_赵玉兰_图文.ppt
数据结构与算法__第三章_清华大学出版社_赵玉兰_理学_高等教育_教育专区。第3...入队操作 void Enter ( DataType item ) { rear->next = new QNode ( ...
数据结构与算法 第三章 树_图文.ppt
数据结构与算法 第三章 树_计算机软件及应用_IT/计算机_专业资料。主讲老师:...= NULL ) { temp = new Node ; temp -> lchild = CopyBT( oldtree->...
第三章 数据结构与算法_线性结构(一)_图文.ppt
第三章 线性结构 ?引子 ?线性表的定义与实现 ?堆栈 ?队列 ?应用实例 第3章 线性结构 §3.1 引子 ? 在数据的逻辑结构中,一种常见而且简单结构是线性结构,...
数据结构与算法第三章2013_图文.ppt
数据结构与算法第三章2013 - 中国民航大学计算机学院数据结构与算法... 数据结构与算法第三章2013_理学_高等教育_教育...{ size=copy.size ; str = new char [...
数据结构与算法分析第三章总结.doc
数据结构与算法分析第三章总结 - 第三章 栈:限定仅在表尾进行插入或删除操作的线
数据结构与算法12(new)_图文.ppt
对于一个较复杂的问题,若能分解为几个相对简单且 解法相同或类似的子问题,只要...数据结构与算法 第三章 ... 88页 免费 第11章_New数据结构与算... ...
数据结构与算法第三章2012_图文.pdf
数据结构与算法第三章2012 - 中国民航大学计算机学院数据结构与算法... 数据结构与算法第三章2012_理学_高等教育_教育...{ size=copy.size ; str = new char [...
数据结构与算法-东北林业大学 第一章演示文稿绪论new_图文.ppt
数据结构与算法-东北林业大学 第一章演示文稿绪论new_IT/计算机_专业资料。数据...{ //算法说明 语句序列 }//函数名 (4)赋值语句: 简单赋值:变量名=表达式;...
川大数据结构与算法分析第三章堆栈和队列_图文.ppt
川大数据结构与算法分析第三章堆栈和队列_工学_高等教育_教育专区。Chapter 3 ...的元素在newr 中对应位置处均为“1”,下一个元素出队 若其在newr中对应...
2009数据结构英文试卷A及答案---NEW.doc
2009数据结构英文试卷A及答案---NEW_IT认证_资格考试/认证_教育专区。北交大数据结构 北京交通大学 2009 年《数据结构与算法设计》试卷 Final examination 2009 Fall...
数据结构与算法基础2016_图文.pdf
数据结构与算法的意义 数据结构 抽象数据类型 算法 算法分析 第1章 绪论 第2...(相当于Pascal语言:new(); C语言:malloc() ) RET(p):结点回收 (相当于...
数据结构与算法(Python语言描述)课件1_图文.ppt
数据结构与算法(Python语言描述)课件 2016 Fall《数据结构第三章 线性表 ...newbase) exit(OVERFLOW); L.elem = newbase; L.listsize += LISTINCREMENT...
基本数据结构与算法_图文.ppt
基本数据结构与算法 - 第三章 基本数据结构与算法 本章主要内容 ? 算法 ? 数据结构 ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? 数据...
数据结构第三章.doc
{ LinkList p; p=new LinkList; p->data=x; p->next=rear->next; //...第三章 数据结构 排序 暂无评价 35页 2下载券 数据结构第三章算法 暂无评价...
数据结构 数据结构与算法第三章 字符串_图文.ppt
数据结构 数据结构与算法第三章 字符串 - 数据结构与算法 第三章 字符串 主讲
数据结构第三章_图文.ppt
/*构造结点*/ q-> rear->next= newnode; q->rear= newnode;/*以尾插法...数据结构第三章算法 暂无评价 22页 1下载券 第3章 数据结构 答案 暂无评价...
工大数据结构第三章作业_图文.doc
数据结构与算法上机作业 第三章树 一、选择题 1、在一棵树中,如果结点 A ...=new node; node* root=new node; node* lc=new node; node* rc=new ...
数据结构与算法设计知识点_图文.doc
第一章 绪论重点内容及要求: 1、 了解与数据结构相关的概念(集合、数据数据...{ // 构造一个空栈 S S.elem = new SElemType[maxsize]; S.top =-1...
更多相关标签: