list.cpp

单链表的相关操作

#include<iostream.h>
#include<stdio.h>
#include<malloc.h>
#define NULL 0
//#define ERROR -1
//#define OK 1

typedef  struct  LNode {
      int      data;  // 数据域
      struct  LNode   *next;  // 指针域
} LNode, *LinkList;

void CreateList_L(LinkList &L, int n) {
    // 逆序输入 n 个数据元素，建立带头结点的单链表
	struct LNode *p;
	L =(LinkList) malloc(sizeof(LNode));  
	L->next = NULL; //建立带头结点的单链表
	for (int i = n; i > 0; --i) {
		p = (LinkList) malloc(sizeof(LNode));
		printf("请输入数据%d\n",i);
		scanf("%d",&p->data);    // 输入元素值
		p->next = L->next;  
		L->next = p;  // 插入
	}//for
	
} // CreateList_L

void printList(struct LNode *L){
	struct LNode *p;
	printf("链表输出如下：\n");
	p=L->next;
	while(p){
		//printf("测试");
		printf("%d\n",p->data);
		p=p->next;
	}
}
int ListInsert_L(LinkList &L,  int i, int e){
	//在带头结点的单链表L中第i个位置前插入元素
	struct LNode *p;
	struct LNode *s;
	p=L;  
	int j=0;
	while(p && j<i-1){
		p=p->next; 
		++j;
	}
	if (!p || j>i-1) return -1;
	s=(LinkList)malloc(sizeof(LNode));
	s->data=e; 
	s->next=p->next;
	p->next=s;
	return 1;
};// LinkList_L	

int ListDelete_L(LinkList L, int i,int &e) {
   // 删除以 L 为头指针(带头结点)的单链表中第 i 个结点
	   
	struct LNode *p;
	struct LNode *q;
	p = L; 
	int j = 0;
	while (p->next && j < i-1) {
		p = p->next;   
		++j; 
	} 
    // 寻找第 i 个结点，并令 p 指向其前趋
	if  (!(p->next) || j > i-1){    
		return -1;  // 删除位置不合理
		printf("删除位置不合理\n");
	}
	q = p->next;   
	p->next = q->next;  // 删除并释放结点
	e = q->data;   
	free(q);
	printf("删除并释放结点\n");
	return 1;
}; // ListDelete_L

int GetElem_L(LinkList L, int i,int &e){
	//L为带头结点的单链表的头指针。
	//当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR
	struct LNode *p;
	p=L->next; 
	int j=1;   //初始化
	while(p && j<i){  //顺序往后找
	  p=p->next; 
	  ++j;
	}
	if ( !p || j>i ){   
		return -1;  //  第 i 个元素不存在
		//printf("第 i 个元素不存在\n");
	}
	else  e=p->data;
	//printf("第 i 个元素:%d\n",p->data);
	return 1;
};//GetElem_L

void main(){
	struct LNode *L;
	int e;
	CreateList_L(L, 6);
	printList(L);
	printf("在第三个位置插入67\n");
	ListInsert_L(L, 3, 67);
	printList(L);
	//ListInsert_L(L, 9, 10);
	//int *e;
	printf("删除第6个元素\n");
	ListDelete_L(L,6,e);
	printf("删除的第6个元素是：%d\n",e);
	printList(L);
	printf("获得第2个元素\n");
	GetElem_L( L, 2,e);
	printf("获得的第2个元素是：%d\n",e);
	printList(L);
}