数据结构实验三 单链表实现学生成绩

1.单链表实现学生成绩

源代码：

1. #include  
2. using namespace std;  
3.   
4. template  
5. struct Node  
6. {  
7.     T data;  
8.     Node *next;  
9. };  
10.   
11. template  
12. class Score  
13. {  
14.     public:  
15.         Score();                        //无参构造函数，建立只有头结点的空链表  
16.         Score(T a[],int n);             //有参构造函数，建立有n个元素的单链表  
17.         ~Score();                       //析构函数  
18.         int Length();                      //求单链表的长度  
19.         T Get(int i);                      //按位置查找，在单链表中查找第i个结点的元素值  
20.         int Locate(T x);                   //按值查找，在单链表中查找值为x的元素序号  
21.         void Insert(int i,T x);            //在第i个位置插入元素值为x的结点  
22.         T Delete(int i);                   //在单链表中删除第i个结点  
23.         void PrintList();  
24.     private:  
25.         Node *first;  
26. };  
27.   
28. template  
29. Score::Score()  
30. {  
31.     first=new Node;      //生成头结点  
32.     first->next=NULL;       //头结点的指针域置空  
33. }  
34.   
35. template                     //尾插法建立单链表  
36. Score::Score(T a[],int n)  
37. {  
38.     Node *r,*s;  
39.     first=new Node;                   
40.     r=first;                            //生成头结点  
41.     for(int i=0;i;s->data=a[i];          //为每个数组元素建立一个结点  
42.         r->next=s;r=s;                           //将结点S插入到终端结点之后  
43.     }  
44.     r->next=NULL;                         //单链表建立完毕，将终端结点的指针域置空  
45. }  
46.   
47. template  
48. Score::~Score()  
49. {  
50.     Node *q;  
51.     while(first!=NULL)                          //释放单链表的每一个结点的存储空间  
52.     {  
53.         q=first;                                 //暂存被释放结点  
54.         first=first->next;                         //first指向被释放结点的下一结点  
55.         delete q;  
56.     }  
57. }  
58.   
59. template  
60. void Score::Insert(int i,T x)  
61. {  
62.     Node *p=first,*s;                   
63.     int count=0;  
64.     while(p!=NULL && countnext;                     
65.         count++;  
66.     }  
67.     if(p==NULL) throw"location";  
68.     else{  
69.         s=new Node;s->data=x;  
70.         s->next=p->next;p->next=s;  
71.     }  
72. }  
73.   
74. template  
75. T Score::Delete(int i)  
76. {  
77.     Node *p=first,*q;  
78.     T x;  
79.     int count=0;  
80.     while(p!=NULL && countnext;  
81.         count++;  
82.     }  
83.     if(p==NULL||p->next==NULL)  
84.         throw"location";  
85.     else{  
86.         q=p->next;x=q->data;  
87.         p->next=q->next;  
88.         delete q;  
89.         return x;  
90.     }  
91. }  
92.   
93. template  
94. int Score::Locate(T x)  
95. {  
96.     Node *p=first->next;  
97.     int count=1;  
98.     while(p!=NULL)  
99.     {  
100.         if(p->data==x) return count;  
101.         p=p->next;  
102.         count++;  
103.     }  
104.     return 0;  
105. }  
106.   
107.   
108. template  
109. void Score::PrintList()      
110. {  
111.     Node *p=first->next;  
112.     while(p!=NULL)  
113.     {  
114.         cout<data<<" ";  
115.         p=p->next;  
116.     }  
117.     cout<  
118. int Score::Length()  
119. {  
120.     Node *p;  
121.     int count;  
122.     p=first->next;count=0;  
123.     while(p!=NULL)  
124.     {  
125.         p=p->next;  
126.         count++;  
127.     }  
128.     return count;  
129. }  
130.   
131. template  
132. T Score::Get(int i)  
133. {  
134.     Node *p;  
135.     int count;  
136.     p=first->next;count=1;  
137.     while(p!=NULL&&count<i>next;  
138.         count++;  
139.     }  
140.     if(p==NULL)throw"location";  
141.     else return p->data;  
142. }  
143.   
144.   
145.   
146.   
147.   
148. int main()  
149. {  
150.   
151.         cout<<"\t ******************学生成绩单链表的实现**************\n";  
152.         cout<<"\t ****************************************************\n";  
153.         cout<<"\t *------------------------------------------*********\n";  
154.         cout<<"\t *****************[1]——输出表长********************\n";  
155.         cout<<"\t *****************[2]——按位查找********************\n";  
156.         cout<<"\t *****************[3]——按值查找********************\n";  
157.         cout<<"\t *****************[4]——插入************************\n";  
158.         cout<<"\t *****************[5]——删除************************\n";  
159.         cout<<"\t *****************[6]——遍历************************\n";  
160.         cout<<"\t *****************[7]——输出主菜单******************\n";  
161.         cout<<"\t *****************[8]——退出************************\n";  
162.         cout<<"\t *------------------------------------------*********\n";  
163.         cout<<"\t ****************************************************\n";  
164.       
165.         int a[]={34,45,56,67,78,83,89,90,95};  
166.         Scores(a,9);  
167.         int flag,i,x,t,l;  
168.         flag=0;   
169.   
170.         while(flag==0)  
171.         {  
172.             cout<<"please input the command(1~8):"<>t;  
173.             switch(t)  
174.             {  
175.             case 1:  
176.                 l=s.Length();                 
177.                 cout<<"the length is:"<>i;  
178.                 x=s.Get(i);       
179.                 cout<<"the number is:"<>x;  
180.                 i=s.Locate(x);  
181.                 cout<<"the location is:"<<i>>i;  
182.                 cout<<"the insert number is:";  
183.                 cin>>x;  
184.                 s.Insert(i,x);  
185.                 cout<<"insert successfully!"<>i;  
186.                 s.Delete(i);  
187.                 cout<<"delete successfully!"<</i></i> 

运行结果：

主界面

输入1  输出表长

输入2 按位查找成绩

输入3 按成绩查找位置

输入6   输出单链表的所有成绩

输入4，把98插入到位置2

输入5，将位于位置5的成绩删除

输入7，输出主界面

输入8，退出程序