Chinaunix首页 | 论坛 | 博客
  • 博客访问: 166871
  • 博文数量: 41
  • 博客积分: 647
  • 博客等级: 上士
  • 技术积分: 366
  • 用 户 组: 普通用户
  • 注册时间: 2011-08-29 14:13
文章分类

全部博文(41)

文章存档

2013年(11)

2012年(1)

2011年(29)

分类: C/C++

2011-12-01 13:55:07

数据结构和算法问题收集
 
链表
 

问题:发现并修复下列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中若NodeNULL,表示从头插入新结点。

 

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

 
 

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

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

// (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

// anodeNULL,表示从头部插入。

// 这里也要考虑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;   
}
阅读(2493) | 评论(0) | 转发(2) |
0

上一篇:栈。。。。

下一篇:排序算法

给主人留下些什么吧!~~