数据结构自己学习整理_副本.pdf

数据结构学习整理 中国海洋大学 信息科学与工程学院 海大新星 2012 年 1 月 7 日星期六 联系：447805280 1 / 36 1.数组和链表的区别。 C++语言中可以用数组处理一组数据类型相同的数据，但不允许动态定义数组的大小，即在 使用数组之前必须确定数组的大小。而在实际应用中，用户使用数组之前有时无法准确确定 数组的大小，只能将数组定义成足够大小，这样数组中有些空间可能不被使用，从而造成内 存空间的浪费。链表是一种常见的数据组织形式，它采用动态分配内存的形式实现。需要时 可以用 new 分配内存空间，不需要时用 delete 将已分配的空间释放，不会造成内存空间的 浪费。 从逻辑结构来看：数组必须事先定义固定的长度（元素个数），不能适应数据动态地增减的 情况，即数组的大小一旦定义就不能改变。当数据增加时，可能超出原先定义的元素个数； 当数据减少时，造成内存浪费；链表动态地进行存储分配，可以适应数据动态地增减的情况， 且可以方便地插入、删除数据项。（数组中插入、删除数据项时，需要移动其它数据项）。 从内存存储来看：（静态)数组从栈中分配空间（用 NEW 创建的在堆中）, 对于程序员方便 快速,但是自由度小；链表从堆中分配空间, 自由度大但是申请管理比较麻烦. 从访问方式来看：数组在内存中是连续存储的，因此，可以利用下标索引进行随机访问；链 表是链式存储结构，在访问元素的时候只能通过线性的方式由前到后顺序访问，所以访问效 率比数组要低。 2.单链表插入元素 #include iostream p=(struct Node using namespace std; *)malloc(LEN); #define LEN sizeof (struct Node) cinp-date; struct Node{ p1-next=p; int date; } struct Node *next; p-next=NULL; }; p=head; int main(){ while (p-next!=0) struct Node *p,*p1,*head; { coutp-date , ; head=p=(struct Node p=p-next; *)malloc(LEN); } cinp-date; coutp-date; while (p-date!=0) return 0; { } p1=p; 3.删除节点值为8的节点： p=head; p=head; if (p==NULL) } { p1=p; exit(0); p=p-next; } while (p!=NULL) while (head-date==8) { {