线性结构------线性表（二）

#include <cstdio>  
#include <cstdlib>  
  
typedef int DataType;  
  
struct LinkList  
{  
    DataType data;  
    struct LinkList *next;  
};  
  
//初始化单链表（将头结点的指针域设置为空，数据域设置为0，数据域代表链表长度）   
   
void InitList(LinkList *L)  
{  
    L->next = NULL;  
    L->data = 0;  
    return;  
}  
  
int ListLength(LinkList *L)   
{  
    return L->data;  
}  
  
void Insert(LinkList *L, int i, DataType e)  
{  
    LinkList *p, *q;  
    p = L;  
    int len = L->data;     
    //i最大为链表长度+1（插到末尾），最小为1       
    if(i > len + 1 || i < 1)  
        printf("Wrong place!\n");         
    //将指针p移动到i的前一个位置   
    for(int j = 1; j < i;j++)  
    {  
        p = p->next;   
    }  
    //找到位置后，新建一个结点,数据域为e   
    q = (LinkList*)malloc(sizeof(LinkList));  
    q->data = e;  
    q->next = p->next;  
    p->next = q;  
    L->data++;  
    return;  
}  
  
DataType GetElem(LinkList *L, int i)  
{  
    LinkList *p;  
    p = L->next;  
    for(int j = 1; j < i; j++)  
    {  
        p = p->next;  
    }  
    return p->data;  
}   
  
int LocateElem(LinkList *L, DataType e)  
{  
    LinkList *p;  
    int i = 1;  
    p = L->next;  
    while(p->data != e && i < L->data)  
    {  
        p = p->next;  
        i++;  
    }  
    if(p->data == e)
	{
    	return i;  
	} 
    if(i == L->data)  
    {  
        printf("No such element!\n");  
        return -1;  
    }  
}  
  
void Delete(LinkList *L, int i, DataType *e)  
{  
    if(i < 1 || i > L->data)  
    {  
        printf("Wrong place!\n");  
        return;  
    }  
    if(L->data == 0)  
    {  
        printf("List is empty!\n");  
        return;  
    }  
    LinkList *p, *q;  
    p = L;  
    //p移动到要删除位置的前面   
    for(int j = 1; j < i; j++)  
    {  
        p = p->next;  
    }  
    //要删除元素赋值给q   
    q = p->next;  
    *e = q->data;  
    //如果q的下一位存在   
    if(q->next)  
    {  
        p->next = q->next;   
    }   
    else  
        p->next = NULL;  
    free(q);  
    L->data--;  
    return;  
}  
  
void PrintList(LinkList *L)  
{  
    for(int i = 1; i <= L->data; i++)  
        printf("%d ", GetElem(L, i));  
    printf("\n");  
}   
  
//销毁链表，包括头结点 
void DestroyList(LinkList *L)  
{  
    LinkList *p;  
    while(L)  
    {  
        p = L;  
        L = L->next;  
        free(p);  
    }  
    return;  
} 
 
//测试代码
int main()  
{  
    LinkList *L = (LinkList*)malloc(sizeof(LinkList));  
    InitList(L);  
    for(int i = 0; i <= 10; i++)  
        Insert(L, i + 1, i);  
    DestroyList(L);  
    InitList(L);  
    Insert(L, 0, 1);  
    Insert(L, 2, 2);  
    Insert(L, 1, 100);  
    PrintList(L);  
    int locate = LocateElem(L, 600);  
    printf("Element 6's place: %d\n", locate);  
    printf("%d\n", L->data);  
    DataType delete_e;  
    Delete(L, 2, &delete_e);  
    PrintList(L);  
    printf("%d\n", L->data);  
    DestroyList(L);  
    printf("%d",GetElem(L, 1));  
    return 0;  
}