第7章_2链表资料.ppt

第7章 结构体、链表与文件系统（2） 思考 能否有一个办法，保证系统资源的最合理运用？ 当我们需要添加一个元素时，程序会自动添加； 当我们需要减少一个元素时，程序会自动放弃该元素原来占有的内存。 动态数据结构 结构体 动态内存分配 链表的定义 struct Link { int data; struct Link *next; }; 链表的定义 struct Link { int data; struct Link *next; }; 链表的定义 struct Link { int data; struct Link *next; }; 链表的定义 struct Link { int data; struct Link *next; }; 链表的基本操作 指针赋值 指针移动 线性链表的基本操作 后插法 前插法 在指定节点p之前插入节点 Lnode *list_insert(Lnode *first,Lnode *p,int e) //节点p之前插入值e { Lnode *q,*s; s=(Lnode *)malloc(sizeof(Lnode));//构造新节点 assert(s!=0); s-data=e; s-next=0; if(first==NULL) //空链表 { first=s; return first; } 在指定节点p之前插入节点 if (p == first)// 将 s 结点插入在链表的第一个结点之前 { s-next=first; first=s; } else { q = first; while (q-next != p ) q = q-next; // 查找 p 的前驱结点 q q-next = s; s-next = p; // 在链表中 q 结点之后插入 s 结点 } return first; } 建立并初始化链表 /* 利用数组a的值建立链表 返回值：返回指针first的值，即返回新链表的首指针 */ Lnode *list_create(Lnode *first,int a[],int n) { int i; for(i=0;in;i++) first=list_insert(first,first,a[i]); //利用前插法建立链表 return first; } 链表的遍历 void list_print(Lnode *first) { Lnode * p; p=first; while(p!=NULL) { printf(%d\t,p-data); p=p-next; /*p指针向后移动*/ } printf(\n); } 删除链表中值为key的节点 Lnode *list_delete(Lnode *first, int key) { Lnode *q=first, *p=first; if(first==NULL) //空链表 return NULL; if(first-data==key) //被删除是首节点 { p=first; first=first-next; return p; } for(q=first;q-next;q=q-next) //被删除节点是中间结点 { p=q-next; if(p-data==key)//找到值为key的节点 { q-next=p-next; //这两条语句删除节点p return p; } } return NULL; //没有找到值为key的节点 } #includestdio.h #includestdlib.h //malloc函数需要的头文件 #includeassert.h //宏assert需要的头文件 typedef struct _lnode { int data; //数据元素 struct _lnode *next; //指向后继节点的指针 }Lnode; main() { int n,a[]={12,34