文章还是关于链表,本次主要涉及几个比较深入的问题:循环链表的判定、倒数第m个节点的数据获取、多层次链表的设计、平铺和取消平铺。
- /*单链表*/
- typedef struct list
- {
- struct list *next;
- int data;
- } List_t, *List_handle_t;
- /*双向链表*/
- typedef struct Dblist
- {
- struct Dblist *next;
- struct Dblist *prev;
- int data;
- }DList_t, *DList_handle_t;
- /*多层次链表*/
- typedef struct mullevel_list
- {
- struct mullevel_list *prev;
- struct mullevel_list *next;
- struct mullevel_list *child;
- int data;
- }MList_t, *MList_handle_t;
关于链表主要还是搞清楚指针的相关问题。链表头的更新操作也是指针操作的一部分,如何实现链表头的自动更新也是需要注意的,如果每次都采用返回值的形式实现链表的头的更新,这在实际的操作中非常的不放便,采用指向指针的指针实现链表头的更新将是非常不错的选择。其实这也是内存分配中经常使用的技巧。
- /*内存分配*/
- bool GetMemory(char ** str, int n)
- {
- *str = (char *) malloc(n);
- if(*str)
- return true;
- return false;
- }
- /*链表头的更新*/
- bool insert_listnode(List_handle_t *head, int a)
- {
- List_handle_t newlistnode = (List_handle_t)malloc(sizeof(List_t)/sizeof(char));
- if(*head == NULL && newlistnode != NULL)
- {
- *head = newlistnode;
- newlistnode->data = a;
- newlistnode->next = NULL;
- return true;
- }
- else if(*head != NULL ** newlistnode != NULL)
- {
- newlistnode->data = a;
- newlistnode->next = *head;
- *head = newlistnode;
- return true;
- }
- return false;
- }
其中这种采用指向指针的指针的方式就能够保证链表的自动更新,这种特性主要是C/C++中函数值传递的特性,形参不改变实参的值,但是当传递的是指针时,这时指针实质上就是地址,作为参数时,地址并不会改变,但是地址中的内容是可改变的,这是内存分配问题中经常使用的技巧,如上面的代码所示。这种代码的形式还有一些优点,可以判断判断问题是否完成,通过判断是否需要再次分配。
单链表的逆序问题:
逆序问题实质上主要是完成每一个链表节点的操作,然后更新链表头,这时需要三个指针,其中一个表示逆序链表的表头,一个表示需要操作的节点,最后一个表示下一个即将操作的节点,也就是逆序操作需要保存三个节点才能保证一个逆序的完成。首先保证下一个即将操作的节点存在,然后实现逆序链表表头与实际操作的节点进行指向操作,更新表头。
- bool reversed_list(List_handle_t *head)
- {
- List_handle_t mid ;
- List_handle_t fir ;
- List_handle_t last;
- if(*head != NULL)
- {
- mid = last = head;
- /*save the node next to be operated*/
- fir = mid->next;
- /*tail of the list*/
- last->next = NULL;
- while(fir != NULL)
- {
- /*get the node to be operated*/
- mid = fir;
- /*save the node next to be operated*/
- fir = fir->next;
- /*link to the head of list*/
- mid->next = last;
- /*update the head of list*/
- last = mid;
- }
- /*return the actual list head*/
- *head = last;
- return true;
- }
- return false;
- }
关于链表是否为循环链表的问题,这种问题是一个经典的问题,因为链表操作实质上就是指针的比较高级的操作。所以一般都需要依仗指针进行操作。如何判断是否为循环呢?如果是像数组那种连续的内存空间可以通过指针的值进行判断,连续性就能使得指针的比较存在意义,但是链表是一个非连续的内存空间,对指针进行比较就没有任何的意义。通常采用快慢指针的形式进行判断。
两个指针,其中一个指针以每次一个对象的形式遍历链表,另一个链表以每次多个对象的形式遍历,如果是非循环的链表,那么快的指针会首先到达链表的尾部。但是如果是循环链表,这时快指针的遍历速度快,因为存在循环,就会存在快指针指向慢指针后面对象的时刻,如果快指针指向的对象就是慢指针指向的对象或者快指针的下一个对象就是慢指针指向的对象(这两种情况都合适,这需要一句循环链表中的对象进行确定),就说明了链表是一个循环链表。快指针的访问速度可以设置为每次两个对象,这样就能实现判断。如下所示:
阅读(917) | 评论(0) | 转发(0) |