Linked Lists
This program illustrates many linked list functions. It shows how to create and manage doubly link lists. It is my most advanced DLL program.
AI
Tóm tắt bởi AI: This codebase represents a historical implementation of the logic described in the metadata. Our preservation engine analyzes the structure to provide context for modern developers.
Mã nguồn
//Jeff Letendre
#include <stdlib.h> //for malloc()
#include <stdio.h> //for printf(), scanf(), fflush()
void main (void); ///////////////////////////////////////
struct node * merge (struct node *, struct node *); ///////////////////////////////////////
struct node * reverse (struct node **); ///////////////////////////////////////
struct node * createList (void); ///////////////////////////////////////
struct node * subtract (struct node *, struct node *); ///////////////////////////////////////
struct node * addSort(int, struct node **); ///////////////////////////////////////
struct node * getMemory(void); ///////////////////////////////////////
struct node * InsertAfter (struct node **); ////////////// prototype //////////////
struct node * intersection (struct node *, struct node *); ////////////// section //////////////
struct node * search (int, struct node *); ///////////////////////////////////////
struct node * bubbleSort (struct node *); ///////////////////////////////////////
void PrintList (struct node *); ///////////////////////////////////////
void deleteNode (struct node **); ///////////////////////////////////////
void free_node (struct node **); ///////////////////////////////////////
int palindrome (struct node *plist); ///////////////////////////////////////
void errorExit (char *); ///////////////////////////////////////
struct node //structure template
{
struct node *previous; //pointer to previous node in list
int data; //integer list data
struct node *next; //pointer to next node in the list
};
////////////END OF HEADER SECTION////////////////
void main (void)
{
struct node *plist = NULL; //pointer for first list
struct node *plist2 = NULL; //pointer for second list
struct node *pnode = NULL; //pointer for node
struct node *tempList = NULL; //misc. pointer for returned lists
int option = 0, choice = 0; //variables for user input
while (true) //main program loop set to infinite loop
{
printf("\n\nPlease make a selection:\n\n"); //prompt for input
printf(" 0 = Add in sorted order\n");
printf(" 1 = Create a list\n");
printf(" 2 = Seek and destroy\n");
printf(" 3 = Exit\n");
printf(" 4 = Search\n");
printf(" 5 = Intersection\n");
printf(" 6 = Print\n");
printf(" 7 = Merge two lists\n");
printf(" 8 = Create another list\n");
printf(" 9 = Palindrome?\n");
printf("10 = Reverse list \n");
printf("11 = Subtract two lists\n");
printf("12 = Insert after\n");
fflush(stdin); //clear input buffer
scanf("%d", &option); //scan new option
switch(option)
{
case 0:
{
printf("Enter an integer to be added to the list or -99999\n");
scanf("%d", &choice);
while (choice != -99999) //call addSort
{
plist = addSort(choice, &plist);
printf("Enter another integer or -99999 to quit\n");
fflush(stdin);
scanf ("%d", &choice);
}
break;
}
case 1:
{
plist = createList();
break;
}
case 2:
{
deleteNode(&plist); //no return modifying original list
break;
}
case 3:
{
exit(1);
break;
}
case 4:
{
printf("Enter a value to search the list for:\n");
scanf("%d", &choice);
tempList = search(choice, plist);
if (tempList == NULL)
{
printf("The value %d was not found in the list\n", choice);
break;
}
else
{
if(tempList->previous == NULL && tempList->next == NULL)
printf("%d is the only value in the list\n", tempList->data);
else if(tempList->previous == NULL && tempList->next != NULL)
printf("%d is the first value in the list followed by %d\n",
tempList->data, (tempList->next)->data);
else if(tempList->previous != NULL && tempList->next == NULL)
printf("%d comes after %d and is the last value in the list\n",
tempList->data, (tempList->previous)->data);
else if(tempList->previous != NULL && tempList->next != NULL)
printf("%d comes after %d and before %dlist\n", tempList->data,
(tempList->previous)->data, (tempList->next)->data);
break;
}
}
case 5:
{
tempList = intersection (plist, plist2);
if(tempList != NULL)
{
tempList = bubbleSort(tempList);
PrintList(tempList);
}
break;
}
case 6:
{
PrintList(plist);
break;
}
case 7:
{
tempList = merge (plist, plist2);
PrintList(tempList);
break;
}
case 8:
{
plist2 = createList();
break;
}
case 9:
{
if(palindrome(plist)) //if palindrome returns 1
{
PrintList(plist);
printf(" it is a palindrome.\n");
}
else
{
PrintList(plist); //else list is not a palindrome
printf(" it is not a palindrome.\n");
}
break;
}
case 10:
{
PrintList(plist); //print list before reversing
printf("\n\nReversing...\n\n");
plist = reverse(&plist); //call to reverse func
PrintList(plist); //print reversed list
break;
}
case 11:
{
printf("How shall I subtract your lists?\n");
printf("1 = First list entered minus second list entered or\n");
printf("2 = Second list entered minus first list entered?\n");
scanf("%d", &choice);
if (choice == 1)
{
tempList = subtract (plist, plist2);
}
else if (choice == 2)
{
tempList = subtract (plist2, plist);
}
else
{
printf("Incorrect choice escaping to main menu\n");
break;
}
PrintList(tempList);
break;
}
case 12:
{
plist = InsertAfter(&plist); //Insert After has capability to
break; //start a new list if plist is empty
}
default:
{
printf("Your only options are zero (0) through eleven (11)\n");
printf("Enter new option\n\n");
break;
}
} //end switch
} //end while
}//////////////end main()/////////////////
struct node * addSort(int newVal, struct node **plist)
{
struct node *newNode;
struct node *ptemp;
ptemp = *plist;
newNode = getMemory(); //call getMemory to allocate and test
newNode->data = newVal; //copy int into struct
while(ptemp != NULL && ptemp->data <= newNode->data && ptemp->next != NULL)
ptemp = ptemp->next;
if(ptemp == NULL) //if list is empty
{
newNode->next = NULL; //set next to NULL
newNode->previous = NULL; //set previous to NULL
*plist = newNode; //set list pointer to newNode
}
else if(ptemp->previous == NULL && ptemp->data > newNode->data)//at begining of list
{
newNode->previous = ptemp->previous;
newNode->next = ptemp;
ptemp->previous = newNode;
*plist = newNode;
}
else if(ptemp->next == NULL) //at end of list
{
newNode->previous = ptemp;
newNode->next = ptemp->next;
ptemp->next = newNode;
}
else if(ptemp->data > newNode->data) //inbetween begining and end of list
{
newNode->next = ptemp;
newNode->previous = ptemp->previous;
(ptemp->previous)->next = newNode;
ptemp->previous = newNode;
}
return(*plist); //pass back list pointer
} ////////////end add sort//////////////////
struct node * bubbleSort (struct node *listHead)//sorts a doubly linked list of ints
{ //returns pointer to sorted list
struct node * listp1 = NULL;
struct node * listp2 = NULL;
listp1 = listHead; //assign pointer to list head
listp2 = listHead->next; //assign pointer to next node
while(listp1 != NULL && listp2 != NULL)
{
if(listp1->data <= listp2->data) //if in ascending order w/ next node
{
listp2 = listp2->next; //skip to next 2 nodes
listp1 = listp1->next;
}
else //else swap order
{
listp1->next = listp2->next;
listp2->previous = listp1->previous;
if(listp1->previous != NULL) //if not the first node
(listp1->previous)->next = listp2; //point previous node's next field to listp2
listp1->previous = listp2;
if(listp2->next != NULL) //if there is a next node
(listp2->next)->previous = listp1; //point its previous field to listp1
listp2->next = listp1;
if(listp1 == listHead) //reset pointers to begining of
listHead = listp2;
listp1 = listHead;
listp2 = listp1->next;
}
} //end while
return listHead;
}///////////////////end bubbleSort///////////////////////
struct node * createList(void)
{
struct node * plist = NULL; //pointer for new list
struct node * temp = NULL; //pointer for inserting into list
struct node * pinsert = NULL; //pointer for node allocation
pinsert = getMemory(); //call getMemory to allocate and test
pinsert->next = NULL; //set node pointers to NULL
pinsert->previous = NULL;
plist = pinsert; //point list pointer to first node
printf("Type a list of integers to be created\n");
printf("Enter -99999 to finish input cycle\n");
printf("Enter first integer for new list\n");
scanf("%d", &(pinsert->data)); //scan new value
while (pinsert->data != -99999)
{
temp = pinsert;
pinsert = getMemory(); //call getMemory to allocate and test
pinsert->next = NULL; //copy NULL to new node's next field
pinsert->previous = temp;
temp->next = pinsert;
printf("Enter an integer to be added after %d:\n", temp->data);
scanf("%d", &(pinsert->data)); //scan into struct's data element value
}
fflush(stdin);
free(pinsert); //free node which contains sentinel (-99999)
temp->next = NULL; //assign last node's next pointer to NULL
return (plist); //returns NULL if list contains sentinel only
} //////////////End createList/////////////
void deleteNode (struct node ** plist) //deletes node from list
{
struct node *temp = NULL;
struct node *next1 = NULL;
int delVal = 0;
next1 = *plist; //set pointer to list head
printf("Enter a value and I will delete all nodes\n");
printf("whose data element matches your value\n");
scanf("%d", &delVal);
while(next1 != NULL) //search through whole list
{
if(next1->data == delVal) //if delVal is found
{
if(next1->next == NULL && next1->previous == NULL) //if deleting only node
{ //deleting only node. Point plist to NULL
free(next1);
*plist = NULL;
}
else if(next1->previous == NULL) //if deleting first node
{
next1 = next1->next; //skip next1 to next node
next1->previous = NULL; //since first node assign previous to NULL
*plist = next1; //point the list pointer to the new first node
free(temp); //free old first node
temp = *plist; //point temp to list
}
else if(next1->next == NULL) //if deleting last node
{
temp->next = NULL; //set temp as last node
free(next1); //free last node in list
next1 = temp->next; //point next1 to NULL;
} //end else
else //else deleting a node between nodes
{
temp->next = next1->next; //shift pointer to skip over node to be deleted
(next1->next)->previous = temp; //point previous element of 1st node after deleted node to temp
free(next1); //free node
next1 = temp->next; //point next1 to next node
} //end else
} //end if
else
{
temp = next1;
next1 = next1->next; //go through list
} //end else
} //end while
}////////////////end deleteNode()///////////////
void errorExit(char *string) //prints error & exits program
{
printf("%s", &string);
exit(1);
}/////////////end errorExit()///////////////
void free_node (struct node **pnode)
{
struct node *ptemp; //temp pointer used for swaping structure pointers
if(pnode == NULL) //if list is empty
errorExit("Attempt to delete from a NULL node pointer");
ptemp == (*pnode)->previous; //point to previous node
ptemp->next = (*pnode)->next; //mend break in links
free(pnode); //release memory back to OS
}/////////end free_node/////////
struct node * getMemory(void) //allocates & tests return value
{
struct node * newPtr = NULL;
if((newPtr = (struct node *) malloc(sizeof(struct node))) == NULL)
{ //if malloc returns a NULL pointer
printf("ERROR! Unable to allocate memory - Abort\n");
abort(); //print error msg & abort function
return(0); //make the compiler happy :>)
}
else
return newPtr;
} ///////////////////end getMemory///////////////
struct node * InsertAfter(struct node **plist)
{
struct node *tempNode;
struct node *tempList;
int afterVal = 0, choice = 0;
tempList = *plist;
tempNode = getMemory(); //call getMemory to allocate and test
if (tempList == NULL) //if list is empty
{
printf("Your list is empty. Should I create a list for you?\n");
printf("1 = Yes\n2 = No\n");
scanf("%d", &choice);
if(choice == 1)
{
printf("Enter an integer\n"); //prompt and get input
while(scanf("%d", &choice) < 1) //testing scanf//reusing choice for data input
printf("Incorrect value entered. Please try again:\n");
tempNode->data = choice;
tempNode->previous = NULL; //set pointers
tempNode->next = NULL;
}
else if(choice == 2) //if user doesn't want to create list
tempNode = NULL; //set return pointer to NULL
return tempNode; //return pointer
} //end if
else //list is not empty
{
printf("Enter an integer to insert the next node after\n");
scanf("%d", &afterVal); //assign new value to data field
for(; tempList != NULL && tempList->data != afterVal; tempList = tempList->next);
if (tempList == NULL)
{
printf("Error list value not found\n"); //print error msg.
return(tempList); //return NULL pointer
}
else if(tempList->data == afterVal)
{
printf("Enter an integer to be added after %d\n", tempList->data);
scanf("%d", &(tempNode->data)); //get new data value
tempNode->next = tempList->next; //assign new node's next field to plist's next field
tempList->next = tempNode; //copy temp into plist's next field
tempNode->previous = tempList; //copy plist to temp's previous field
}
} //end else
return (*plist);
}///////////End InsertAfter////////////
struct node * intersection (struct node *opList1, struct node *opList2)
{
struct node *temp = NULL;
struct node *intList = NULL;
temp = getMemory();
intList = temp; //list head pointer
if(opList1 == NULL || opList2 == NULL)
{
printf("Empty list(s) - can not take intersection\n");
temp = NULL;
return temp;
}
while (opList1 != NULL)
{
if(search(opList1->data, opList2) != NULL)
{ //if data is not in list
temp->previous = opList1->previous; //copy node into new list
temp->data = opList1->data;
temp->next = getMemory(); //allocate more memory
(temp->next)->previous = temp; //point next nodes previous field to current node
temp = temp->next; //point temp to next node
opList1 = opList1->next;
} //end if
else
opList1 = opList1->next;
} //end while
(temp->previous)->next = NULL; //terminate links w/ NULL
free(temp); //release extra node back to OS
return intList;
} /////////////end intersection////////////////
struct node * merge (struct node *listA, struct node *listB)
{
struct node * listHead = NULL; //pointer to new merged list
listHead = listA; //set pointers to begining of listA
while (listA->next != NULL) //skip to end of listA
listA = listA->next;
listB->previous = listA; //append listA with listB
listA->next = listB;
listHead = bubbleSort(listHead); //sort new list
return listHead; //return pointer to new merged sorted list
} ////////////end merge//////////////////
int palindrome (struct node *plist)
{
struct node *temp1;
struct node *temp2;
int i = 0, j = 0;
temp1 = temp2 = plist; //set both temp vars to the list pointer
for (i=0; temp2->next != NULL; temp2 = temp2->next, i++); //terminated for loop to move to end of list
for(j = 0; j < i; j++)
{
if (temp1->data != temp2->data) //if values not equal
return (0);
else
{
temp1 = temp1->next; //increment temp1
temp2 = temp2->previous; //decrement temp2
}
} //end for loop
return(1);
} ///////////end palendrome///////////////
void PrintList (struct node *plist)
{
int i = 0;
if(plist != NULL)
{
printf("Here is your list:");
while (plist != NULL)
{
if((i % 10) == 0) //CRLF first line then print ten values per line
printf("\n");
printf("--> %d ", plist->data);
plist = plist->next; //point plist to next node
i++;
} //end while loop
} //end else statement
} ///////////////end PrintList()////////////////
struct node * reverse (struct node ** plist)
{
struct node *rList = NULL;
struct node *ptemp = NULL;
struct node *pt2 = NULL;
ptemp = *plist;
while(ptemp->next != NULL)
{
ptemp = ptemp->next; //point ptemp to end of list
}
rList = ptemp;
*plist = rList; //set list pointer to end of list
while(ptemp != NULL)
{
ptemp = ptemp->previous;
rList->previous = rList->next;
rList->next = ptemp;
rList = ptemp;
}
return(*plist);
} //////////end reverse////////////////////
struct node * search (int data, struct node *pstack)
{
struct node *ptemp;
for (ptemp=pstack; ptemp != NULL && ptemp->data != data; ptemp = ptemp->next);
return ptemp; //returns NULL if data not found
}///////////end of search///////////////
struct node * subtract (struct node *opList1, struct node *opList2)
{
struct node *temp = NULL;
struct node *subList = NULL;
temp = getMemory();
subList = temp; //list head pointer
while (opList1 != NULL)
{
if(search(opList1->data, opList2) == NULL)
{ //if data is not in list
temp->previous = opList1->previous; //copy node into new list
temp->data = opList1->data;
temp->next = getMemory(); //allocate more memory
(temp->next)->previous = temp; //point next nodes previous field to current node
temp = temp->next; //point temp to next node
opList1 = opList1->next;
} //end if
else
opList1 = opList1->next;
} //end while
(temp->previous)->next = NULL; //terminate links w/ NULL
free(temp); //release extra node back to OS
return subList;
}//////////end subtract////////////////
/////////////////////////////////// END PROGRAM /////////////////////////////
function mstrGetRelativeURL()
mstrGetRelativeURL=Request.serverVariables("PATH_INFO")
end function
Upload
<?php
// $Id: authticket.phl,v 1.3 1998/02/11 16:45:34 explorer Exp $
//
// Copyright (c) 1998 Michael Graff <[email protected]>
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions
// are met:
// 1. Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
// 2. Redistributions in binary form must reproduce the above copyright
// notice, this list of conditions and the following disclaimer in the
// documentation and/or other materials provided with the distribution.
// 3. Neither the name of author nor the names of its contributors may be
// used to endorse or promote products derived from this software
// without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND ANY
// EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
// WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
// DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS BE LIABLE
// FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
// DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
// SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
// CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
// LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
// OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
// SUCH DAMAGE.
//
class authticket {
var $secret = "setme"; // you WILL want to change this
var $realm = ""; // the realm of this identity
var $lifetime = 2 * 60 *60; // tickets good for 2 hours
var $authenticated = 0; // the data here is valid iff non-zero
var $identity; // the remote identity, if decoded correctly
var $issue; // the time the ticket was issued
var $remote_addr; // the remote address of the client
var $hash; // the hash value. Probably of little use.
var $autherr; // if verification faild, this contains why
//
// helper function which just zeros out the ticket data
//
function zerodata()
{
$this->authenticated = 0;
$this->identity = "";
$this->issue = 0;
$this->remote_addr = "";
$this->hash = "";
$this->autherr = "";
}
//
// Take a string ($identity) and a time ($time) and the internal
// secret value, and generate a string that can be used to verify
// that the remote user is known to us. The result of this function
// is a single string, that can be passed along in a hidden form
// or even a cookie.
//
// If ($time) is 0, the current time is used instead.
//
// ($identity) _cannot_ contain a ``:'' character. If you need
// one in there, you will have to change it to some sort of escape
// sequence.
//
// Some care should be used. I recommend using this only over SSL,
// unless the actual ticket contents are encrypted using something
// stronger than XOR.
//
function makeauth($identity, $time)
{
global $REMOTE_ADDR;
$this->zerodata();
if ($time == 0)
$time = time();
$ticket_items[] = (string)$time;
$ticket_items[] = $this->realm;
$ticket_items[] = $REMOTE_ADDR;
$ticket_items[] = $identity;
$ticket = implode($ticket_items, ":");
$hash = md5($this->secret . $ticket);
$ticket = $hash . ':' . $ticket;
$this->identity = $identity;
$this->issue = $time;
$this->remote_addr = $REMOTE_ADDR;
$this->hash = $hash;
$this->authenticated = 1; /* data is valid */
$this->autherr = "";
return $ticket;
}
//
// Take a ($ticket) string generated by makeauth(), and a ($time),
// and verify that the ticket is valid and not expired.
//
// If ($time) is 0, the current time will be used.
//
// On error, the function returns the empty string "",
// $authenticated is 0, and $autherr contains the reason
// the authentication failed.
//
// On success, the identity encoded in the ticket is returned,
// $authenticated is non-zero, and $autherr is to be ignored.
//
function checkauth($ticket, $time)
{
global $REMOTE_ADDR;
$this->zerodata();
if ($time == 0)
$time = time();
/*
* Item order: hash time realm remote_addr identity
*/
$ticket_items = explode(":", $ticket);
/*
* if the remote address doesn't match the one in the ticket,
* drop them.
*/
if ($ticket_items[3] != $REMOTE_ADDR) {
$this->autherr = "Address mismatch";
return "";
}
//
// if we are supposed to check for expired tickets, do that
// here.
//
if ($this->lifetime != 0)
if ($time > (int)$ticket_items[1] + $this->lifetime) {
$this->autherr = "Ticket expired";
return "";
}
//
// make certain that the ticket is not being used before
// it was issued.
//
if ($time < (int)$ticket_items[1]) {
$this->autherr = "Ticket used before issued";
return "";
}
//
// verify that the realms match
//
if ($this->realm != $ticket_items[2]) {
$this->autherr = "Realm mismatch";
return "";
}
//
// This could be done better... Reassemble the components
// of the ticket passed to us, and rehash. Compare this
// to the hash we were sent.
//
$tmp_items[] = $ticket_items[1];
$tmp_items[] = $ticket_items[2];
$tmp_items[] = $ticket_items[3];
$tmp_items[] = $ticket_items[4];
$tmp_ticket = implode($tmp_items, ":");
$hash = md5($this->secret . $tmp_ticket);
if ($hash != $ticket_items[0]) {
$this->autherr = "Integrity check failed";
return "";
}
//
// well, it all checks out. Might as well claim we know
// who this person is.
//
$this->hash = $hash;
$this->issue = $ticket_items[1];
$this->remote_addr = $ticket_items[3];
$this->identity = $ticket_items[4];
$this->authenticated = 1;
return $this->identity;
}
};
?>
DropDownList.SelectedIndex = DropDownList.Items.IndexOf(New ListItem("ABC"))
or
DropDownList.SelectedItem.Text = "ABC"
Bình luận gốc (3)
Được khôi phục từ Wayback Machine