数据结构概述

（1） 定义：我们如何把现实中大量而复杂的问题已特定的

数据类型和特定的存储结构保存到主存储器(内存)中，以及

在此基础上位实现某个功能二执行的相应操作，

这个相应的操作也叫算法。

解释：数据结构要解决的问题就是把现实中大量复杂的问题存储到内存中，把单个数据的类型确定，再把数据之间关系确定，这样就可以存储到内存中去了，算法就是对数据结构的操作。比如数组是一个数据结构，单个数据类型就确定，数据之间关系就是连续存储，操作数组就是一个算法。侠义的算法是依附于某个数据结构上，也就是说同样对数组遍历和对链表遍历，算法肯定不一样。

数据结构解决存储问题，算法解决数据间的关系。

数据结构=个体+个体的关系

算法=对存储数据的操作。

狭义的算法

算法：解题的方法和步骤

（2）衡量算法的标准：1时间复杂度

大概程序要执行的次数，而非执行

的时间：运行步骤最多的最关最核心的要运行的次数

可以大概代表

2空间复杂度：算法执行过程中大概

所占有的最大内存。

3 难易程度

4健壮性

前两个最重要

（一般算法有循环）

（3）第三个内容：数据结构的地位

（数据结构是软件中最核心的课程）

数据库和数据结构的区别：

数据库是数据结构的简化版

程序：数据的存储+数据段操作+可以被计算机之行的语言

（4）预备知识：

伪算法不是真正的算法

通过语言来实现伪算法，希望编程语言实现要通过指针。

链表的知识很重要，以后都会用到。C++的指针不够，学

C语言的用途是为了以后能看懂更高级的语言

p就代表一个变量，例如i 。intp表示定义一个存放整

形变量的地址的指针变量。

程序运行完，内存就终止了。

复习：

1:指针：

int *p//p 是个变量名字，用来存放地址，只能存储int型变量的地址

指针的重要性：是C语言的灵魂，

定义

内存单元的编号（cpu只能访问内存，不能访问硬盘）

从0开始的非负整数，范围为0——4g-1

指针就是地址，地址就是指针

指针变量是存放内存单元地址的变量

指针和指针变量不一样

指正的本质是一个操作受限的非负整数

分类：

Int *p;

Int *j;

Int i=10;

P=&I;//(1).把i的地址赋给i，p就指向了I (2).p和i没有任何的关系 (3)p就是i

P=10//error

I=*j//error

1 基本类型的指针（p=&i表示指针变量存储i的地址，但是p为p，i为i两者无任何关系，

但是*p和i却是等效的两者可以互换）

变量不进行初始化，会是一个随机数的原因。

2:指针结构体

3:动态内存的分配和释放。

4：内存的基本单位是字节

5：&为取地址符号

6:

# include <stdio.h>

void f(int *p)

{

 *p=100

 }

int main()

{

 int i=9；

 f(&i)

 printf("i=%d\n",i);

return 0

}

@@如何实现被掉函数修改主调函数中普通变量的值

1：实参为相关变量的地址（&i）

2：形参为以该变量的类型（int型）为类型的指针变量（指针变量p）

3：在被调函数中通过 *形参变量名 的方式就可以修改主函数中普通变量的值

（*p和i可以等效替换两者无任何区别）

指针和数组（Array）

数组名

一位数组名a是个指针常量//

int a[]={1,2,3,4,5};//在内存中开辟了一个连续的5个整形变量的内存空间。它们是共生共亡。

它存放的是一维数组第一个元素的地址，、】

它的值不能被改变//&a[1]=….是错误的！

一维数组名指向的是数组的第一个元素。

下表和指针的关系

a[i]<<==>>*（a+i）下标和指针的关系

假设指针变量的名字为p

则p+i的值是p+i*（p所指向的变量所占的字节数）

指针变量的运算

指针变量不能相加，乘除。

如果两指针变量属于同一数组，则可以相减

指针变量可以相减一整数，前提是最终结果不能草果指针的范围

p+i的值是p+i* (p所指向的变量所占的字节数)

p-i的值是p-i* (p所指向的变量所占的字节数）

p++《==》p+1

如何通过被调函数修改主函数中一位数组的内容

两个参数

存放数组首元素的指针变量

存放数组元素长度的整形变量

# include《stdio.h》

void show-array（int *p ，int len）

{

p[2]=-1;//p[0]==*p p[2]==*(p+2)==*(a+2)==a[2]//p【i】此时就是主函数的a【i】

}

int main (void )

{

int a[5]={11,2,3,4,5};

show_arraya(a,5)//a等价于&a[0],&a[0]本身就是int *类型

return 0

}

一个double占八个字节，一个字节是8位，美一个字节都占一个地址。

指针变量都只占四个字节（无论指针变量指向的对象占多少字节，它只占4个字节。）

指针变量只占4个字节原因：在32位的操作系统中，一共有32根地址总线，可以有2的32次方大小的地址编码，所以需要4个字节的大小来表示，所以32位的操作系统中，指针的大小是4个字节。

p=&x 表示p只代表x的第一个字节的地址

如何通过函数修改实参的值

#include <stdio.h>

void f（int * q）//函数声明

int main (void)

{

 int i=9;

 int*p=&i；// 等效为int *p; p=&i;

printf ("%p\n",p)；//%P 表示输出指针变量所指向的元素的地址例如此例中就输出的事i的地址。

 return 0;

}

void f( int **q)

{

 *q=(int *)0xFFFFFFFF；//（int*）表示强制转换0xFFFFFFFF为地址，如果不强制转换0xFFFFFFFF只表示一个十六进制的数

}

如果想改写一个变量的值，只需要发送它的地址给被掉函数，否则无法实现对主函数中变量的值的改变。

结构体：

为什么会出现结构体：为了表示一些复杂的数据，而普通的基本类型变量无法满足要求

什么叫结构体：（是 c++中类的过度）是用户根据实际需要自己定义的复合数据类型

如何使用结构体：struct Student={1000,”zhangshan”,20};

结构体 Struct sudent * pst =&st;

1;

st.sid

pst->sid

Pst所指向的结构体中的sid这个成员

注意事项；结构体变量不能加减乘除，但是可以相互赋值

普通结构体变量和结构体指针变量作为函数传参的问题

#include<stdio.h>

#include<string.h>//一串，一行

struct 结构体Student

{

 int sid;

 char name[200];

 int age;

};//分号不能省

int main(void)

{

 struct Student st={1000,"zhangshan",20};

 printf("%d %s %d\n",st.sid,st.name,st.age);

 st.sid=99;

 strcpy(st.name,"lisi");//st.name="lisi";error

 st.age=22;

 printf("%d %s %d\n",st.sid,st.name,st.age);

 //printf("%d %s %d\n",st);

 return 0;

}

结构体2

#include<stdio.h>

#include<string.h>//一串，一行

struct 结构体Student

{

 int sid;

 char name[200];

 int age;

};//分号不能省

int main(void)

{

结构体

  Struct Student st={1000，“张三”，20}；

 //st.sid=99;第一种方式

 Struct Student* pst；//定义一个指针变量，此指针变量只能存放我们自己定义的Struct Student类型的变量的地址

 Pst=&st;

 Pst->sid=99;//pst->sid等价于（*pst）.sid 而（*pst）.sid等价于st.sid,所以pst->sid=st.sid

 return 0；

}

第八次课:

结构体：

1：为什么会出现结构体

为了表示一些复杂的数据，而普通的基本类型变量无法满足要求

2：什么叫做结构体

用户根据实际需要自己定义的复合数据类型

3：如何使用结构体

算法1：

# include<stdio.h>

struct Student

{

 int sid;

 char name[100];

 int age;

} ;

int main ()

{

 struct Student st = {

 2013213990,"wangchuankun",20

 };

 printf ("%d %s %d\n",st.sid,st.name,st.age);

 return 0;

}

输出结果：

————————————--

2013213990 wangchuankun 2

请按任意键继续. . .

有两种方式：

1：

4：注意事项

结构提变量不能加减乘除，但是可以相互赋值。

结构提变量和结构体指针变量作为函数传参

算法2：算法目的：通过结构体调用指针给主函数中结构体变量赋值

#include <stdio.h>

#include <string.h>

struct Student

{

 int sid;

 char name[200];

 int age;

} ;

void f(struct Student *pst)

{

 (*pst).sid = 2013213990;

 strcpy (pst->name,"wangchuankun");

 pst->age = 22;

}

int main ()

{

 struct Student st;

 f(&st);

 printf ("%d %s %d\n",st.sid,st.name,st.age);

 return 0;

}

运行结果：

——————————————————

2013213990 wangchuankun 22

请按任意键继续. . .

——————————————————

算法3：算法目的：通过结构体调用指针给主函数中结构体变量赋值

并且通过函数调用将主函数中的结构体变量依次输出。

#include <stdio.h>

#include <string.h>

struct Student

{

 int sid;

 char name[100];

 int age;

} ;

void f(struct Student *pst)

{

 (*pst).sid = 2013213990;

 strcpy(pst->name,"汪传坤");

 pst->age = 20;

}

void g(struct Student *pst)

{

 printf (" 学号：%d\n 姓名：%s\n 年龄：%d\n\n",pst->sid,pst->name,pst->age);

}

int main()

{

 struct Student st;

 f (&st);

 g (&st);//*g(st)**速度慢，并且耗内存*

 return 0;

}

运行结果：

学号：2013213990

姓名：汪传坤

年龄：20

请按任意键继续. . .

跨函数使用内存必须要通过动态分配来完成！

例题：怎样使得指针变量p指向一个合理的整形单元。

*A *

*Void foo(int * p){*

 *int I;*

 *p=&I;*

*}*

*int mian(){*

 *Int *p;*

 *Foo(p);*

 *Return 0;*

*}*

*B*

*Void foo(int **p){*

 *Int I;*

 **p=&I;*

*}*

*Int main(){*

 *Int *p;*

 *Foo(&p);*

*}*

*C*

*Void foo(int **p){*

 **p=(int *)malloc(4);*

*}*

*Int main(){*

 *Int *p;*

 *Foo(&p);*

*}*

*D*

*Void foo(int **p){*

 **p=(int *)malloc(4);*

*}*

*Int main(){*

 *Int *p;*

 *Foo(&p);*

 *Free(p);*

*}*

练习程序：

*#include <stdio.h>*

*#include<malloc.h>*

*void foo(int **p){*

 **p=(int *)malloc(sizeof(int));*

 ***p=1000;*

*}*

*int main(){*

 *int *p;*

 *foo(&p);*

 *printf("%d\n",*p);*

 *free(p);*

 *return 0;*

*}*

*看懂以下程序：*

*#include <stdio.h>*

*#include <malloc.h>*

*struct Student{*

 *int age;*

 *int num;*

*};*

*Student * get(Student ** ps){*

 **ps=(Student *)malloc(sizeof(Student));*

 *(*ps)->age=12;*

 *(*ps)->num=44;*

 *return *ps;*

*}*

*void show(Student * ps){*

 *printf("%d%d\n",ps->age,ps->num);*

 *free(ps);*

*}*

*int main(){*

 *Student *s1;*

 *s1=get(&s1);*

 *show(s1);*

 *return 0;*

*}*

算法4：跨函数使用内存必须通过动态分配内存来实现

# include <stdio.h>

# include <malloc.h>

int f(int**q)

{

 int i;

 *q = (int *)malloc(16);//*malloc**函数返回的是第一个字节的地址，但是这个地址没有类型，所以要强制转换一下。*

 /*for (i = 0;i<4;i++)

 {

 printf ("%d\n",q[i]);

 }

 */

 return 0;

}

int main ()

{

 int i;

 int *p;

 f (&p);

 for (i = 0;i < 4;i++)

 {

 scanf ("%d",&p[i]);

 }

 for (i = 0;i<4;i++)

 {

 printf ("%d\n",p[i]);

 }

 return 0;

}

运行结果：

78

45

89

12

78

45

89

12

请按任意键继续. . .

算法总结：通过把指针变量的地址发给形参变量q（int*q表示q是存放int类型变量的地址q本身是一个变量， ）

算法5：

# include <stdio.h>

# include <malloc.h>

struct Student

{

 int sid;

 int age;

};

struct Student *CreateStudent(void);

void ShowStudent (struct Student *);

int main ()

{

 struct Student *ps;

 ps = CreateStudent();

 ShowStudent(ps);

 return 0;

}

void ShowStudent(struct Student *pst)

{

 printf ("%d %d\n",pst->sid,pst->age);

}

struct Student * CreateStudent(void)

{

 struct Student *p = (struct Student *)malloc(sizeof(struct Student));

 p->sid = 99;

 p->age = 88;

 return p;

}

运算结果：

99 88

请按任意键继续. . .

注：只能通过动态分配内存通过调用函数分配内存才有效。