链表的实现

好像终于明白一点了。。

#include <iostream>
using namespace std;

typedef struct node *link;
struct node{
        int data;
        link next;
};
static link head = NULL;
link makeNode(int data);
void freeNode(link p);
void deleteNode(link p);
void insertNode(link p);
void traverseList(void (*visit)(link p));
void printNode(link p);
void destroyList();
int countListItem();
void insertNodeAt(link p,int index);

int main(int argc, char* argv[])
{
        link p = makeNode(3);
        insertNode(p);
        insertNode(makeNode(4));
        insertNode(makeNode(5));
        traverseList(printNode);
        //cout<<"before delete: "<<countListItem()<<endl;
        insertNodeAt(makeNode(7),2);
        traverseList(printNode);
        insertNodeAt(makeNode(6),3);
        traverseList(printNode);
        insertNodeAt(makeNode(8),10);
        traverseList(printNode);
        destroyList();
        cout<<"after destroyList : "<<countListItem()<<endl;
        return 0;
}

void printNode(link p)
{
        cout<<p->data<<" ";
}

link makeNode(int data)
{
        link p = new struct node;
        p->data=data;
        p->next=NULL;
        return p;
}

void insertNode(link p)
{
        p->next=head;
        head=p;
}

void traverseList(void (*visit)(link p))
{
        link p;
        for(p=head;p;p=p->next)
                visit(p);
        cout<<endl;
}

void freeNode(link p)
{
        delete [] p;        //释放的是指针指向的地址空间，而并非删除指针变量
}

void destroyList()
{
        link q, p = head;
        head = NULL;
        while (p) {
                q = p;
                p = p->next;
                freeNode(q);
        }
}

int countListItem()
{
        link p;
        int num=0;
        for(p=head;p;p=p->next)
                num++;
        return num;
}
void insertNodeAt(link p, int index)
{
        link q=head;
        int num=countListItem();
        if(index>num+1)
        {
                cout<<"overflow,error"<<endl;
                return;
        }
        for(int i=0;i<index-1;i++)
        {
                q=q->next;
        }
        cout<<"current data: "<<q->data<<endl;
        p->next=q->next;
        q->next=p;
        //cout<<"insert at "<<index<<" succedd!"<<endl;
}

线性表的链表表示LinkedList

一般使用链表来描述。
优点：对于新增和删除操作add和remove和方便。不需要移动元素。

缺点：不方便随机访问元素，LinkedList要移动指针

代码实现：

// Test.cpp : Defines the entry point for the console application.  
//  
#include "stdafx.h"  
#include <stdio.h>  
#include "stdlib.h"  
//宏定义  
#define TRUE   1  
#define FALSE   0  
#define OK    1  
#define ERROR   0  
#define INFEASIBLE -1  
#define OVERFLOW -2  
  
#define LT(a,b)   ((a)<(b))  
#define N = 100         
  
typedef int Status;  
typedef int ElemType;  
  
typedef struct LNode{  
    ElemType  data;               
    struct LNode   *next;     
}LNode, *LinkList;  
  
/************************************************************************/  
/* 
初始化链表 
*/  
/************************************************************************/  
Status initList(LinkList &L){  
    /*单链表的初始化*/  
    L = (LinkList)malloc(sizeof(LNode));    //申请一个头节点  
    if(!L) exit(OVERFLOW);          //申请空间失败    
    L->next=NULL;                //建立一个带都节点的空链表  
    return OK;  
  
    /*  
    需要改变指针的指针，所以参数必须是引用或者是 *L: 
    (*L) = (Lnode *)malloc(sizeof(Lnode)); 
    (*L)->next=NULL; 
    return 1;                                                                      
    */  
  
}  
  
/************************************************************************/  
/*      
创建链表 
*/  
/************************************************************************/  
void createList(LinkList L, int n){  
    /*单链表的初始化*/  
    if (!L) {  
        initList(L);  
    }  
    ElemType data;  
    LinkList p,q = L;  
    printf("输入节点数据的个数%d：\r\n", n);  
    for(int i = 0; i<n; i++) {  
        p = (LinkList) malloc( sizeof(LNode)); //申请一个新节点  
        scanf("%d",&data);  
        p->data = data;  
        p->next = q->next;  
        q->next = p;  
        q = p;  
    }  
}  
/************************************************************************/  
/* 在第i位置插入e 
*/  
/************************************************************************/  
Status insertList(LinkList L, ElemType e, int i){  
    LinkList s, p = L;  
    int j = 0;  
    while (p && j<i){                //寻找i节点  
        p = p->next;  
        j++;  
    }  
    if (!p ||j >i) return ERROR;  
    s = (LinkList) malloc(sizeof(LNode));       //生成新节点  
    s->data = e; s->next = p->next;            //插入L中  
    p->next = s;  
    return OK;  
  
}  
  
/************************************************************************/  
/* 删除第i位置元素，并用e返回其值                                                                     */  
/************************************************************************/  
Status deleteListElem(LinkList L, int i, ElemType &e){  
    LinkList p, q;  
    int j = 0;  
    p = L;  
    while (p && j<i){  
        p = p->next;  
        ++j;  
    }  
    if (!p->next || j>i)  return ERROR;   //删除的位置不对  
    q  = p->next; p->next = q->next;  
    e = q->data; free(q);            //释放节点  
    return OK;  
}  
  
  
/************************************************************************/    
/*  插入排序  
*/    
/************************************************************************/    
  
void  InsertSort(LinkList L)  
{  
    LinkList  list;             /*为原链表剩下用于直接插入排序的节点头指针*/  
    LinkList  node;             /*插入节点*/  
    LinkList  p;          
    LinkList  q;          
  
    list = L->next;              /*原链表剩下用于直接插入排序的节点链表*/  
    L->next = NULL;              /*只含有一个节点的链表的有序链表。*/  
    while (list != NULL)   {    /*遍历剩下无序的链表*/  
        node = list, q = L;     
        while (q && node->data > q->data  ) {  
            p = q;  
            q = q->next;  
        }  
          
        if (q == L) {  /*插在第一个节点之前*/  
            L = node;  
        }  else {     /*p是q的前驱*/  
            p->next = node;     
        }  
        list = list->next;  
        node->next = q; /*完成插入动作*/  
  
    }  
}  
  
  
  
/************************************************************************/  
/*  
合并两个线性表 
*/  
/************************************************************************/  
  
void mergeList(LinkList  &La, LinkList  &Lb,  LinkList &Lc){  
    LinkList pa, pb, pc;  
    pa  = La->next;  
    pb  = Lb->next;  
    Lc =  pc = La;  
    while (pa && pa) {  
        if (pa->data > pb->data) {  
            pc->next = pb;  
            pc = pb;  
            pb =pb->next;  
        }else{  
            pc->next = pa;  
            pc = pa;   
            pa =pa->next;  
        }  
    }  
    pc->next = pa? pa :pb;  
    free(Lb);  
}  
  
/************************************************************************/  
/* 打印list 
*/  
/************************************************************************/  
void printList(LinkList  L){  
    printf("当前值:");  
    LinkList p;  
    p = L->next;  
    while(p){  
        printf("%d ", p->data);   
        p = p->next;  
    }  
    printf("\r\n");   
}  
  
void main()  
{  
    LinkList  La,Lb,Lc;  
    ElemType e;  
    int init,i;  
    printf("LA:\r\n");    
    initList(La);  
    createList(La, 5);  
    insertList(La, 7,  3);    
    printList(La);  
    deleteListElem(La, 3,  e);    
    printList(La);  
    InsertSort(La);  
    printList(La);  
  
    printf("Lb:\r\n");    
    initList(Lb);  
    createList(Lb, 4);  
    InsertSort(Lb);  
    printList(Lb);  
  
    printf("Lc:\r\n");   
    initList(Lc);  
    mergeList(La,   Lb,   Lc);  
    printList(Lc);  
  
}