数据结构-单链表
一、单链表
1：单链表的定义：
2：尾插法创建单链表：
3：头插法创建单链表：
4：输出单链表上各结点值；
5：在单链表上查找第i个位置上的结点，并将结点值输出；
6：在单链表head中第i个位置上插入元素值为x的新结点；
7：判断单链表是否为空；
8：删除单链表上第i个位置上的结点；
9：删除整个单链表

一、单链表
1：单链表的定义：
#include "stdio.h"   
typedef int datatype;
typedef struct node
{
  datatype data;
  struct node *next;
}linklist;

2：尾插法创建单链表：
linkList* Creatlist(datatype a[ ], int n)
{   linklist *head,rear;    
    head=(linklist*)malloc(sizeof(linklist)) ;
     rear=head;   
    for (i=0; i<n; i++)
    {  s=(linklist*)malloc(sizeof(linklist)) ;
        s->data=a[i];   //scanf(“%d”,&s->data);
        rear->next=s;        
        rear=s;
     }
     rear->next=NULL;
     return head;
 }

3：头插法创建单链表：
linkList* Creatlist(datatype a[ ], int n)
{   linklist *head,rear;    
    head=(linklist*)malloc(sizeof(linklist)) ;
    for (i=0; i<n; i++)
    { s=(linklist*)malloc(sizeof(linklist)) ; 
	  s->data=a[i];
      s->next=head->next;
      head->next=s;
     }
     return head;
 }

4：输出单链表上各结点值；
void displaylist(linklist *head)
{
	linklist *p;//活动指针
    p = head->next;   
    while(p) {   
        printf("%d ",p->data);   
        p=p->next;   
    } 
    printf("\n");  
}

5：在单链表上查找第i个位置上的结点，并将结点值输出；
datatype Get(linklist *head,int i) 
{
     linklist *p;int j;
     p=head->next;  j=1;  
     while (p && j<i)    
     {
         p=p->next; 
         j++;      
     }
     if (!p)   {printf(“第i个元素不存在”);exit(0);}
     else return p->data;  
}

另一种描述：注意返回值
linklist* Get( linklist *head, int i) 
{
     linklist *p;int j;
     p=head->next;  j=1;  
     while (p && j<i)    
     {
         p=p->next; 
         j++;      
     }
     if (!p)   {printf(“第i个元素不存在”);return NULL;}
     else return p;  
}

6：在单链表head中第i个位置上插入元素值为x的新结点；
 void Insert(linklist *head,int i, datatype x)
 {   linklist *p,*s;   
     p=head ;   j=0;    //分析p=head->next ?   j=1? 分别是否可以？为什么？
     while (p && j<i-1)
     {
          p=p->next; 
          j++;
     }//p=Get(head,i-1);
   if (!p) 
    printf(“结点i不存在！”); 
   else { 
 s=(linklist*)malloc(sizeof(linklist)) ;
       s->data=x;  
       s->next=p->next;       
       p->next=s;
   }
}

7：判断单链表是否为空；
/*判断链表head是否为空，为空返回1,否则返回0*/
int isEmpty(linklist *head)
{
	if(head->next) return 0;
	else return 1;
}

8：删除单链表上第i个位置上的结点；
void Delete(linklist *head,int i)
{  linklist *p,*q;  
    p=head ; j=0;  
    while (p && j<i-1)
    {
         p=p->next;
         j++;
     }//p = Get(head,i-1);
   if (!p | | !p->next) 
        printf(“结点不存在！”); 
   else {  
         q=p->next; 
         x=q->data;   
         p->next=q->next;   
         free(q); 
	}
 }

9：删除整个单链表
void Deletelist(linklist *head)
{   linklist *p,*q;
    p=head; 
    while (p)
  {
        q=p;    
        p=p->next;  
        free( q);    
    }
}

学习数据结构创建单链表
创建单链表的两种方法：头插法，尾插法

基本运算：

制空表
判空表
求表长
查找数据值为X的元素
查找线性表中第i个元素
在线性表第I个元素之前插入数据为X的结点
在系欸点P之后插入一个数据值为X的结点
删除线性表的第I个元素
删除结点q的直接后继
显示线性表的数据元素值

直接上代码：

定义接口
package ds.linklist;
/***
 * 线性表的抽象数据类型
 * @author 1
 *
 */
public interface IList {
 public void clear(); //置空表
 public boolean isEmpty();//判空表
 public int length();//求表长
 public Object indexOf(Object x)throws Exception;//查找数据值为x的元素
 public Object get(int i)throws Exception; //查找线性表中第i个元素
 public void insert(int i,Object x)throws Exception; //在线性表第i个元素之前插入数据为x的结点
 public void insert(Node p,Object x)throws Exception; //在结点p之后插入一个数据值为x的结点
 public void remove(int i)throws Exception; //删除线性表的第i个元素
 public void remove(Node q)throws Exception; //删除结点q的直接后继
 public void display(); //显示线性表的数据元素值
}
package ds.linklist;
/***
 * 单链表的结点类型
 * @author 1
 *
 */
public class Node {
 //数据域
 public Object data;
 //指针域
 public Node next;
 //构造方法
 //无参数时的构造方法
 public Node() {
  super();
 }
 //带一个参数时的构造方法
 public Node(Object data) {
  super();
  this.data = data;
 }
 //带两个参数时的构造方法
 public Node(Object data, Node next) {
  super();
  this.data = data;
  this.next = next;
 } 
}
写方法：

初始化一下

public class Linklist implements IList {
// 头指针
public Node head;
// 构造方法：创建头结点
public Linklist() {
  head = new Node();// 初始化头结点
 }
}

尾插法代码块

// 尾插法创建单链表
 public void creatR() {
  Scanner input = new Scanner(System.in);
  Node s, r = head;
  int i = 0;
  System.out.print("请输入第" + i + "个数据元素值：");
  Object x = input.next();
  while (!x.equals("$")) {
   s = new Node(x); // 创建新的结点
   s.next = r.next; // 将结点插入到表尾
   r.next = s;
   r = s;
   i++;
   System.out.print("请输入第" + i + "个数据元素值：");
   x = input.next();
  }
  r.next = null;
 }

头插法代码块

// 头插法创建单链表
 public void creatH() {
  Scanner input = new Scanner(System.in);
  Node s;
  int i = 0;
  System.out.print("请输入第" + i + "个数据元素值：");
  Object x = input.next();
  while (!x.equals("$")) {
   s = new Node(x); // 创建新的结点
   s.next = head.next; // 将结点插入到表头
   head.next = s;
   i++;
   System.out.print("请输入第" + i + "个数据元素值：");
   x = input.next();
  }
 }

置空表代码块

public void clear() {
  head.data = null; 
  head.next = null;
 }

判空表代码块

public boolean isEmpty() {
  return head.next == null;
 }

求表长代码块

public int length() {
  //将p初始指向链表中第一个结点的地址
  Node p=head.next;
  int length=0;
  while(p!=null){
   p=p.next;
   ++length;
  }
  return length;
 }

查找数据值为X的代码块

public Object indexOf(Object x) throws Exception {
  Node p = head.next;
  int j = 1;
  while (p != null && !p.data.equals(x)) {
    p = p.next; // 查找下一个结点
    j++;
  }
  if (p == null) {
   return -1;
  } else
   return j;
 }

查找线性表中第 i 个元素代码块

public Object get(int i) throws Exception {
  int j = 0;
  Node p = head;
  while (p != null && j < i) {
   p = p.next;
   j++;
  }
  if (p == null)
  throw new Exception("第" + i + "个元素不存在");
  return p;
 }

在线性表第i个元素之前插入数据为x的结点代码块

public void insert(int i, Object x) throws Exception {
  Node p = (Node) get(i - 1);
  Node s = new Node(x);
  s.next = p.next;
  p.next = s;
 }

在结点p之后插入一个数据值为x的结点代码块

public void insert(Node p, Object x) throws Exception {
  Node s = new Node(x);
  Node q = head;
  while (q.next != p)
   q = q.next;
  s.next = p.next;
  p.next = s;
 }

删除线性表的第i个元素代码块

public void remove(int i) throws Exception {
  Node p = (Node) get(i - 1);//定位第i-1个结点
  remove(p);//
 }

删除结点q的直接后继代码块

public void remove(Node q) throws Exception {
  Node s = q.next;
  q.next = s.next;
 }

显示线性表的数据元素值代码块

public void display() {
  Node node = head.next;
  while (node != null) {
   if (node == head.next) {
    System.out.print("head->"+node.data);
   } else
    System.out.print("->" + node.data);
   node = node.next;// 取下一个结点
  }
 }
测试类：
public class Demo1 {
	public static void main(String[] args) {		  
	  Scanner input = new Scanner(System.in);
	  System.out.println("*****主菜单*****");
	  System.out.println("1:利用尾插法创建一个单链表");
	  System.out.println("2:利用头插法创建一个单链表");
	  System.out.println("3、退出系统");
	  System.out.print("请输入你想选择的功能：");
	  int choice = input.nextInt();
	  // 创建Linklist的对象
	  Linklist list = new Linklist();
	  switch (choice) {
	  case 1:
	   // 采用尾插法创建单链表
	   list.creatR();
	   System.out.println("使用尾插法创建的单链表如下所示：");
	   // 显示所创建的链表
	   list.display();
	   break;
	  case 2:
	   // // 采用头插法创建单链表
	   list.creatH();
	   System.out.println("使用头插法创建的单链表如下所示：");
	   // // 显示所创建的链表
	   list.display();
	   break;
	  case 3:
	   System.exit(0);
	   break;
	  default:
	   System.out.println("请输入正确的指令！");
	   System.out.println("");
	  }
	  while (true) {
	   System.out.println("--------------------");
	   System.out.println("1、显示该链表的长度");
	   System.out.println("2、在单链表的第i个位置插入数据值为x的元素");
	   System.out.println("3、删除单链表中的第i个结点");
	   System.out.println("4、删除单链表中值为x的结点");
	   System.out.println("5、置空表");
	   System.out.println("6、退出系统");
	   System.out.println("请输入你想选择的功能：");
	   int function = input.nextInt();
	switch (function) {
	   case 1:
	    System.out.println("单链表长度为：" + list.length());
	    break;
	   case 2:
	    System.out.println("请输入要插入的位置：");
	    int i = input.nextInt();// 输入想要插入的结点位置
	    System.out.println("请输入要插入元素的数据值：");
	    Object x = input.next();// 输入想要插入的值
	    try {
	     list.insert(i, x);// 调用方法
	     list.display();
	     System.out.println("");
	    } catch (Exception e) {
	     // TODO Auto-generated catch block
	     e.printStackTrace();
	    }
	    break;
	   case 3:
	    System.out.println("----删除单链表中第i个结点----");
	    i = input.nextInt();// 输入想要删除的结点位置
	    try {
	     list.remove(i);
	     list.display();
	     System.out.println("");
	    } catch (Exception e) {
	     // TODO Auto-generated catch block
	     e.printStackTrace();
	    }
	    break;
	   case 4:
	    System.out.println("----删除单链表中值为x的结点----");
	    System.out.println("请输入想要删除的结点的值：");
	    // list.remove(q, x);
	    try {
	     x = input.next();
	     int a = (Integer) list.indexOf(x);
	     //Node q =(Node) list.indexOf(x);
	     list.remove(a);
	     list.display();
	     System.out.println("");
	     // list.remove(q);
	    } catch (Exception e1) {
	     // TODO Auto-generated catch block
	     e1.printStackTrace();
	    }
	    break;
	   case 5:
	    list.clear();
	    System.out.println("链表已置空！");
	    break;
	   case 6:
	    System.exit(0);
	    break;
	   default:
	    System.out.println("请输入正确的指令！");
	   }	
 	}
     }
 }
测试功能一切正常，基本运算没有完全加到测试类里面，该文章仅供自己复习和提供一些思路给大家，如果有发现的错误，麻烦大家及时指出。

验证单链表及其上的基本操作
目录
目的
内容及要求
实验过程
算法设计
代码编写
程序调试
测试数据设计
结果
总结

目录
目的
验证单链表及其上的基本操作
内容及要求

定义单链表类。
实验验证如下算法的正确性、各种功能及指标：

1）创建单链表；

2）插入操作：分别在当前结点后、表头、表尾插入值为x的结点；

3）删除操作：分别删除表头结点、表尾结点和当前结点的后继结点；

4）存取操作：分别存取当前结点的值和单链表中第k个结点的值；

5）查找操作：查找值为x的元素在单链表中出现的位置（是链表中的第几个元素）。
为便于观察程序的运行结果，设计的输出函数能在屏幕上以规范、直观的形式输出计算结果。例如将链

表输出成如下形式：[1]->[2]->[3]->[4]->[5]
测试程序时，对所有输入变量取遍各种有代表性的值。
为了增强程序的可读性，程序中要有适当的注释。

实验过程
算法设计、代码编写、程序调试、测试数据设计、测试
算法设计
先编写有关单链表操作的各个函数：

InitList(LinkList *&L);

DestroyList(LinkList *&L);

ListEmpty(LinkList *L);

ListLength(LinkList *L);

DispList(LinkList *L);

GetElem(LinkList *L,int i,ElemType &e);

LocateElem(LinkList *L,ElemType e);

ListInsert(LinkList *&L,int i,ElemType e);

ListDelete(LinkList *&L,int i,ElemType &e);

之后的五个函数对应主函数中的五项功能，通过选择结构语句确定执行哪项功能。

代码编写
#include <stdio.h> 
#include <malloc.h> 
typedef char ElemType; 
typedef struct LNode	/*定义单链表结点类型*/ 
    { 	
        ElemType data;
		struct LNode *next; 
		 } LinkList; 
		 
		void InitList(LinkList *&L) 
    { 	
		 L=(LinkList *)malloc(sizeof(LinkList)); 	/*创建头结点*/ 	
		 L->next=NULL; 
		 
		 }
		void DestroyList(LinkList *&L) 
	{ 	
	      LinkList *p=L,*q=p->next; 	
		while (q!=NULL) 	
		{ 		
		   free(p); 		
		   p=q; 		
		   q=p->next; 	
		   } 	
		   free(p); 
		   } 
		int ListEmpty(LinkList *L) 
    { 	
		  return(L->next==NULL); 
		  } 
		int ListLength(LinkList *L) 
	{ 	
	      LinkList *p=L;
		  int i=0; 	
		  while (p->next!=NULL) 	
		  { 		
		    i++; 		
		    p=p->next; 	} 	
			return(i); 
		} 
		void DispList(LinkList *L) 
	{ 	
	      LinkList *p=L->next;
		  while (p!=NULL) 	
		  { 		
		    printf("%c",p->data);
		    p=p->next; 	
			} 	
			printf("\n"); 
		} 
		int GetElem(LinkList *L,int i,ElemType &e)   //查找值 
	{ 	
	      int j=0; 	
		  LinkList *p=L; 	
		  while (j<i && p!=NULL) 	
		  { 		
		    j++; 		
			p=p->next; 	} 	
			if (p==NULL || i<1) // 当超出上界或者下界时，查询失败 	
			{ 		
			  printf("您输入的元素位置数据不合法！\n"); 		
			  return 0; 	
			  }else 	
			  { 		
			    e=p->data; 		
				return 1; 	
				} 
			} 
			int LocateElem(LinkList *L,ElemType e)    //查找位置 
		{ 
		     LinkList *p=L->next; 	
			 int n=1; 	
			 while (p!=NULL && p->data!=e) 	
			 { 		
			   p=p->next; 		
			   n++; 	
			   } 	
			 if (p==NULL) 		
			  return(0); 	
			 else 		
			  return(n); 
			  } 
			int ListInsert(LinkList *&L,int i,ElemType e)   //插入节点 
		{ 	  
		      int j=0; 	
			  LinkList *p=L,*s; 	
			while (j<i-1 && p!=NULL) 	
		    { 		
		      j++; 		
			  p=p->next; 	
			  } 	
			  if (p==NULL || i<=0)	/*未找到第i-1个结点*/ 	
			  { 		
			    printf("插入失败！\n"); 		
				return 0; 	
				}else			/*找到第i-1个结点*p*/ 	
				{ 	s=(LinkList *)malloc(sizeof(LinkList));	/*创建新结点*s*/ 		
				    s->data=e;								 		
					s->next=p->next;						/*将*s插入到*p之后*/ 		
					p->next=s; 		
					printf("插入完成！\n") ; 		
					return 1; 	
					  } 
			} 
			int ListDelete(LinkList *&L,int i,ElemType &e)    //删除节点 
		{ 	  int j=0; 	
		      LinkList *p=L,*q; 	
			  while (j<i-1 && p!=NULL) 	
			  { 		
			    j++; 		
				p=p->next; 	} 	
			  if (p==NULL || i <1 ||q==NULL )				/*未找到第i-1个结点*/ 	
			  { 		
			    return 0; 	
				}else						/*找到第i-1个结点*p*/ 	
				{ 	q=p->next; /*q指向要删除的结点*/ 
				    e=q->data; 		
					p->next=q->next;		/*从单链表中删除*q结点*/ 	 
					free(q);				/*释放*q结点*/ 	 
					return 1; 	} 
			} 
            
//             void InitList(LinkList *&L); 
//			   void DestroyList(LinkList *&L); 
//			   int ListEmpty(LinkList *L); 
//			   int ListLength(LinkList *L); 
//			   void DispList(LinkList *L); 
//			   int GetElem(LinkList *L,int i,ElemType &e); 
//			   int LocateElem(LinkList *L,ElemType e); 
//			   int ListInsert(LinkList *&L,int i,ElemType e); 
//			   int ListDelete(LinkList *&L,int i,ElemType &e); 

        int three(LinkList *h,int pos,ElemType &e){
        	Sur:printf("\n请输入你要查询的数据元素的位置（数字）："); 	
			   scanf("%d", &pos) ; 	
			   if(GetElem(h,pos,e)) 	
			   { 		
			     printf("单链表h的第%d个元素=%c\n", pos, e); 	
				 } 	else { 		
				     printf("查询失败！\n"); 
				SurEle:	printf("你是否要继续查询？(Y/N)") ; 		
					   getchar(); 
					   char ele;		
					   scanf("%c", &ele) ; 		
					   switch (ele)
					   { 		
					     case 'Y': 		
						 case 'y': goto Sur ; break; 		
						 case 'N': 		
						 case 'n': printf("您选择放弃再次查询！\n") ; break; 
						default: printf("您输入的数据不合法！请重新输入：\n"); goto SurEle ; break; 		
						} 	
						} 
		}
		int two(LinkList *h,ElemType e){
			SurCon:printf("\n请输入你要查找的数据元素的值：") ; 	
					   getchar(); 	
					   scanf("%c", &e) ; 	
					   if (LocateElem(h,e)) 	
					   { 		
					     printf("查找成功，元素%c的位置=%d\n", e, LocateElem(h,e)); 	
						 } 	else 	{ 		
						      printf("查询失败！你输入的数据元素的值不存在！\n") ; 
				SurConEle:	printf("你是否要继续查询？(Y/N)") ; 		
				            getchar(); 
							char ele;		
							scanf("%c", &ele) ; 		
							switch (ele) 		
							{ 		
							  case 'Y': 		
							  case 'y': goto SurCon ; break; 		
							  case 'N': 		
							  case 'n': printf("您选择放弃再次查询！\n") ; break; 
						default: printf("您输入的数据不合法！请重新输入：\n"); goto SurConEle ; break; 		
						    } 	
						} 	
		}
		int one(LinkList *h){
			printf("\n请输入你要插入的数据元素的位置和数据元素值（以逗号隔开）："); 
			int pos;
			ElemType e;
						scanf("%d,%c", &pos, &e); 	
						if (ListInsert(h, pos, e)) 	
						{ 			
						  printf("输出成功插入元素后的单链表h:"); 			
						  DispList(h); 	
						} 
		}
		int four(LinkList *h,int pos,ElemType &e){
				Dle:printf("\n请输入你要删除的数据元素的位置："); 	
				     //getchar(); 	
					 scanf("%d", &pos) ; 	
					 if(ListDelete(h,pos,e)) 	
					 { 		
					   printf("删除成功！你删除的位置的数据元素值为%c\n", e) ; 		
					   printf("输出成功删除元素后单链表h:"); 		
					   DispList(h); 		
					   printf("你是否要继续删除？(Y/N)") ; 		
					   getchar(); 
					   char ele; 		
					   scanf("%c", &ele) ; 		
					   switch (ele) 		
					   { 		
					     case 'Y': 		
						 case 'y': goto Dle ; break; 		
						 case 'N': 		case 'n': printf("您选择不再继续删除！\n") ; break; 
						default: printf("您输入的数据不合法！请重新输入：\n"); goto Dle ; break; 		
						} 	
					} 	else 	
					   { 		
					     printf("删除失败！请检查你输入的数据元素的位置!\n") ; 
					DleEle:	printf("你是否要继续再次尝试删除？(Y/N)") ; 		
					        getchar(); 
							char ele;		
							scanf("%c", &ele) ; 		
							switch (ele) 		
							{ 		
							  case 'Y': 		
							  case 'y': goto Dle ; break; 		
							  case 'N': 		
							  case 'n': printf("您选择放弃尝试删除！\n") ; break; 
						default: printf("您输入的数据不合法！请重新输入\n"); goto DleEle ; break; 		
						} 	
						}
		}
		int five(LinkList *h){
			    printf("\n释放单链表h。。。\n"); 	
				DestroyList(h); 
				printf("\n释放单链表h成功！！\n");
				
		}
			int main() { 	
			   int pos; 	
			   LinkList *h; 	
			   ElemType e; 	
			   	
			   printf("(1)初始化单链表h\n"); 	
			   InitList(h); 	
//			   printf("\n(2)依次插入a,b,c元素\n"); 	
//			   ListInsert(h, 1, 'a'); 	
//			   ListInsert(h, 2, 'b'); 	
//			   ListInsert(h, 3, 'c'); 	
//			   printf("\n(3)输出单链表h:"); 	
//			   DispList(h); 	
//			   printf("\n(4)单链表h长度=%d\n",ListLength(h)); 	
//			   printf("\n(5)单链表h为%s\n",(ListEmpty(h)?"空":"非空")); 
			   
			   int choice;
	  while(1){
	  printf("\n\n1:插入元素\n2:查询元素的位置\n3:查询元素的值\n4:删除元素\n5:释放单链表\n");
	  scanf("%d",&choice);
	  switch(choice){
	  	case 1:one(h);break;
	  	case 2:two(h,e);break;
	  	case 3:three(h,pos,e);break;
	  	case 4:four(h,pos,e);break;
	  	case 5:five(h);break;
	  }
    }
			   
		return 0;		
			} 




程序调试

单链表的操作main.cpp	[Error] ‘pos’ was not declared in this scope

进行分析后发现错误是由于并未在函数中声明pos的类型，当把pos声明为int类型时，错误消失。
单链表的操作main.cpp	[Error] too few arguments to function ‘int two(LinkList*, ElemType)’

进行分析后发现错误是由于调用函数时传参不够，当把e传进去后，错误消失。

测试数据设计
先输入1，选择插入元素功能；然后输入1，a；在第一个节点插入a；

之后再输入2，b；在第一个节点后插入b；

再输入3，c；在第二个节点后插入c；

再输入2，选择查询元素位置功能；然后输入b；返回2；

再输入3，选择查询元素的值功能；然后输入1，返回a；

再输入4，选择删除元素功能；然后输入1，返回删除成功,输出b,c；

再输入5，选择释放单链表功能；返回释放成功。
结果



总结

程序运行过程中有许多冗杂的地方，还有许多需要改进的地方。
关于错误方面，构造存储结构时需要注意字母的大小写。还有遇到输入数据错误时应加上返回语句return 0,否则会出现程序检查时没有错误但运行时出现内存错误的提示。在函数调用时函数的形参不能写类型。

线性表：简称表，是n个具有相同类型的数据元素的有限序列。

线性表的长度：线性表中数据元素的个数。

特性：有限性、相同性、顺序性。

线性表分顺序表、单链表。

Operation LnitList：表的初始化

DestoryList: 销毁表

Length：求表的长度

Get：在表中去序号为i的数据元素

Locate：在数据表中查找值为x的数据元素

Insert：在i处插入一个新元素x

Delete：删除表中第i个元素

Empty：判断元素是否为空

PrintList：遍历表