数据结构-链表相关

数据结构和算法问题收集

 

链表

 

问题：发现并修复下列C函数中的问题和缺陷，该函数从一个单项链表中删除头元素。

void removeHead(Node *head)

{

         delete head;

         head = head->next;

}

 

解答：首先是传入的值问题，头指针本来定义的就是一个指针，它的内容是一个结点地址的值，若要在函数中通过传递参数改变head本身的值，需要传递该参数的地址，也就是head的地址，所以这里需要使用**head；

比如：int *a;

要通过传递参数的方法改变a的值，若使用：

Int b=9;

Void change(int *a)

{

         a = &b;

}

这样是做不到的。

因为没有返回值，所以下面的写法才合乎情理：

void removeHead(Node **head)

{

         Node *pnode;

        

         if (!(*head)) {

                   pnode = (*head)->next;  //把下一个结点指针保存下来

                   delete *head;           //释放头指针指向结点的空间

                   *head = pnode;          //改变头结点的指针值

         }

}

 

 

问题：ghead 和 gtail分别是指向链表的头结点和尾结点的全局指针，实现一下函数：

        

struct node {

    int data;

    struct node *next;

};

typedef struct node Node;

         bool remove(Node *node);

         bool insertAfter(Node *node, int data);

在insertAfter中若Node为NULL，表示从头插入新结点。

 

解答：此题看起来简单，但要考虑的问题并不少，所以要把软件写出来很容易，但要写出稳定、高效的软件是相当难的。

 

 

// 这种由全局变量来操作的链表是相当常见的。

// 主要要考虑三种情况：

// (1)删除头结点： 一定要记得更新头指针的值

// (2)删除尾结点： 一定要记得更新尾结点的值

// (3)删除中间结点： 注意和删除尾结点相整和起来

// 只要能注意到这些，问题就不大了。

int remove_gnode(Node *dnode)

{

    Node *pnode = ghead;

 

    if (NULL == dnode)          //正确性检测

        return 0;

       

    if (dnode = ghead) {        //若删除的是头结点

        ghead == dnode->next;    //改变头结点的指针就可以了

        free(dnode);            //释放dnode结点空间

           

        if (NULL == ghead)   //注意:还要考虑链表只有一个结点,正好该结点被删除的情况.

            gtail = NULL;       //此时把头和尾指针都要置空.

        return 1;

    }  

           

    while (pnode) {

        if (pnode->next == dnode) {

            pnode->next = dnode->next;      //一般情况下的删除操作

            free(dnode);

 

            if (NULL == pnode->next) {      //注意：若删除的是尾结点,

                gtail = pnode;              //      必须更新尾结点的指针值

            }  

            return 1;

        }   

        pnode = pnode->next;

    }

 

    return 0;

}

 

// insert a new node whose data is 'data' after anode

// 若anode为NULL，表示从头部插入。

// 这里也要考虑3中情况，一种是从头插入，一种是从尾部插入，一种是中间插入。

// (1)头部插入: 注意空链表时,尾指针必须更新,一般情况尾部指针不需要更新

// (2)尾部插入: 注意更新尾指针的值

// (3)中间插入: 一般处理

int insert_gnode(Node *anode, int data)

{

    Node *pnew, *ppos = ghead;

  

    pnew = (Node *)malloc(sizeof(Node));    //构建新结点           

    if (NULL == pnew)

        return 0;

    memset(pnew, 0, sizeof(Node));

    pnew->data = data;

 

    if (NULL == anode) {        //从链表头插入新结点

        pnew->next = ghead;     //next指向以前头指针指向的结点

        ghead = pnew;           //头指针变成新结点的指针

 

        if (NULL == gtail)      //空链表情况

            tail = pnew;        //尾指针也变成新结点地址

        return 1;

}

while (ppos) {  //一般情况

     if (anode == ppos) {    //找到结点指针位置

         pnew->next = anode->next;  

         anode->next = pnew;

 

         if (NULL == pnew->next) //插入的位置是尾结点，需要更新尾巴指针

             gtail = pnew;

         return 1;

     }

     pnew = pnew->next;

 }

  

 free(pnew);     //失败

 return 0; 

}

 

 

问题：实现一个链表的反转

//[head]->[p0]->[p1]->[p2]->[...]

//[head]->[p0]<-[p1]  [p2]

//始终要使得3个指针以同样的先后顺序分别指向先后的3个节点。

Node *reverse_link(Node *head)
{
    Node *p0 = NULL;
    Node *p1 = NULL;
    Node *p2 = NULL;

 

    p0 = head;
    p1 = p0->next;

    while (p1) {
        p2 = p1->next;   //向前移动
        p1->next = p0;   //开始反转，从中间节点开始
        p0 = p1;         //移动最前面的指针到中间
        p1 = p2;         //移动中间的指针到最后一个指针位置
    }  

    head->next = NULL;   //头指已经变为尾指针，必须把NEXT字段设置为NULL
    head = p0;           //重置头指针；这里要注意不是p1，而是p0，假设3个节点推导一下就知道
    return head;
}

 

 

 

//不移动数据，只操作指针来交换链表中相邻的两个元素

/*
 * 交换两个相邻的链表元素,
 * 交换元素n和n+1的值.
 */
Lnode *exchange(Lnode *h, int n)
{
    int i; 
    Lnode *p1, *p2, *p3;
            
    p1 = h;
    p2 = p1->next;
    i = 1;

    while (NULL != p2) {
        p3 = p2->next;
        if (i == n)
            break;
        p1 = p2;       
        p2 = p3;   
        i++;
    }  
               
    //exchange
    p1->next = p3; 
    p2->next = p3->next;
    p3->next = p2;

    return h;   
}